排序和搜索的经典问题假设了被比较对象的一个基本线性排序。在本文中我们基于偏序背景研究了这些问题，其中对象的某些对不可类比。从组合角度来看，这种概括很有趣，且它可在例如会议提交的非基于线性排序排名场景中有直接应用。它也可应用于例如包括生物网络的某些类型网络的重构中。与二十年前由Faigle和Turán所创结果相比，我们的研究结果展示了显著进步。尤其是我们首次提出与最佳查询复杂度O(n(w + log n))相一致的 n容量w宽度的算法。我们还描述了查询复杂度O(wn log n/w)总复杂度为O(w2n log n/w)的归并分类变量；由Faigle和Turán定义的具有相同查询复杂度的算法，但是仍无法有效实现该算法。我们的这两种排序算法可以伴随极小开支被应用到重构传递关系的更普遍问题中。 我们也考虑了两个相关问题： 找到最小元素归纳它从而找到底端k“水平”，即k-选择问题。我们为寻找最小元素给出了有效的O(wn)查询和总复杂度的确定性和随机化算法。我们因子至多为2的查询复杂度提供匹配下限并将其结果推广到k-选择问题中。最后，我们提出用于计算偏序线性扩展并计算所有元素高度的有效算法。
Classical problems of sorting and searching assume an underlying linear ordering of the objects being compared. In this paper, we study these problems in the context of partially ordered sets, in which some pairs of objects are incomparable. This generalization is interesting from a combinatorial perspective, and it has immediate applications in ranking scenarios where there is no underlying linear ordering, e.g., conference submissions. It also has applications in reconstructing certain types of networks, including biological networks. Our results represent significant progress over previous results from two decades ago by Faigle and Turán. In particular, we present the first algorithm that sorts a width-w poset of size n with optimal query complexity O(n(w + log n)). We also describe a variant of Mergesort with query complexity O(wn log n/w) and total complexity O(w2n log n/w); an algorithm with the same query complexity was given by Faigle and Turán, but no efficient implementation of that algorithm is known. Both our sorting algorithms can be applied with negligible overhead to the more general problem of reconstructing transitive relations. We also consider two related problems: finding the minimal elements, and its generalization to finding the bottom k "levels", called the k-selection problem. We give efficient deterministic and randomized algorithms for finding the minimal elements with O(wn) query and total complexity. We provide matching lower bounds for the query complexity up to a factor of 2 and generalize the results to the k-selection problem. Finally, we present efficient algorithms for computing a linear extension of a poset and computing the heights of all elements.
ABOUT THE AUTHOR
Associate Professor at MIT's Electrical Engineering and Computer Science department, a member of CSAIL, and affiliated with LIDS and ORC.