# Distribution-sensitive set multi-partitioning

Abstract : Given a set $\mathcal{S}$ with real-valued members, associated with each member one of two possible types; a multi-partitioning of $\mathcal{S}$ is a sequence of the members of $\mathcal{S}$ such that if $x,y \in \mathcal{S}$ have different types and $x < y$, $x$ precedes $y$ in the multi-partitioning of $\mathcal{S}$. We give two distribution-sensitive algorithms for the set multi-partitioning problem and a matching lower bound in the algebraic decision-tree model. One of the two algorithms can be made stable and can be implemented in place. We also give an output-sensitive algorithm for the problem.
Keywords :
Type de document :
Communication dans un congrès
Conrado Martìnez. 2005 International Conference on Analysis of Algorithms, 2005, Barcelona, Spain. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms, pp.353-356, 2005, DMTCS Proceedings
Domaine :

Littérature citée [12 références]

https://hal.inria.fr/hal-01184216
Contributeur : Coordination Episciences Iam <>
Soumis le : jeudi 13 août 2015 - 13:34:46
Dernière modification le : jeudi 11 mai 2017 - 01:02:54
Document(s) archivé(s) le : samedi 14 novembre 2015 - 10:23:19

### Fichier

Fichiers éditeurs autorisés sur une archive ouverte

### Identifiants

• HAL Id : hal-01184216, version 1

### Citation

Amr Elmasry. Distribution-sensitive set multi-partitioning. Conrado Martìnez. 2005 International Conference on Analysis of Algorithms, 2005, Barcelona, Spain. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms, pp.353-356, 2005, DMTCS Proceedings. 〈hal-01184216〉

### Métriques

Consultations de la notice

## 54

Téléchargements de fichiers