# 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 :
Document type :
Conference papers
Domain :

Cited literature [12 references]

https://hal.inria.fr/hal-01184216
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Thursday, August 13, 2015 - 1:34:46 PM
Last modification on : Thursday, May 11, 2017 - 1:02:54 AM
Long-term archiving on: : Saturday, November 14, 2015 - 10:23:19 AM

### File

Publisher files allowed on an open archive

### Citation

Amr Elmasry. Distribution-sensitive set multi-partitioning. 2005 International Conference on Analysis of Algorithms, 2005, Barcelona, Spain. pp.353-356, ⟨10.46298/dmtcs.3381⟩. ⟨hal-01184216⟩

Record views