Distribution-sensitive set multi-partitioning
Distribution-sensitive set multi-partitioning
复制标题
分布敏感集多分区
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
Amr Elmasry
中科院分区：
文献类型：
--
作者：
Amr Elmasry
给定一个具有实值成员的集合\(\mathcal{S}\)，每个成员关联两种可能类型中的一种；\(\mathcal{S}\)的多重划分是\(\mathcal{S}\)成员的一个序列，使得如果\(x,y\in\mathcal{S}\)具有不同类型且\(x<y\)，那么在\(\mathcal{S}\)的多重划分中\(x\)排在\(y\)之前。我们针对集合多重划分问题给出了两个对分布敏感的算法以及在代数判定树模型中的一个匹配下界。这两个算法中的一个可以是稳定的并且可以原地实现。我们还针对该问题给出了一个对输出敏感的算法。
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.