Skip to Main content Skip to Navigation
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.
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/hal-01184216
Contributor : Coordination Episciences Iam <>
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

Identifiers

  • HAL Id : hal-01184216, version 1

Collections

Citation

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

Share

Metrics

Record views

71

Files downloads

483