| HAL-Inria | Publications, software ... of Inria's scientists |
Conference papers
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.
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
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
dmAD0132.pdf
Publisher files allowed on an open archive