Sorting and Selection in Posets
Authors:
- Constantinos DaskalakisCDConstantinos Daskalakis
- Richard M. KarpRKRichard M. Karp
- Elchanan MosselEMElchanan Mossel
- Samantha J. RiesenfeldSRSamantha J. Riesenfeld
- Elad VerbinEVElad Verbin
- 1 January 2011
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 40 (3) , 597-622
Abstract
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 query complexity $O(n(w+\log n))$ and prove that this query complexity is asymptotically optimal. We also describe a variant of Mergesort with query complexity $O(wn\log\frac{n}{w})$ and total complexity $O(w^{2}n\log\frac{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 query complexity and total complexity $O(wn)$. 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.
Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- The Number of Linear Extensions of the Boolean LatticeOrder, 2003
- The Structure and Function of Complex NetworksSIAM Review, 2003
- Balanced pairs in partial ordersDiscrete Mathematics, 1999
- Balancing pairs and the cross product conjectureOrder, 1995
- A random polynomial-time algorithm for approximating the volume of convex bodiesJournal of the ACM, 1991
- Sorting and Recognition Problems for Ordered SetsSIAM Journal on Computing, 1988
- The Information-Theoretic Bound is Good for MergingSIAM Journal on Computing, 1984
- Balancing poset extensionsOrder, 1984
- A Counting Approach to Lower Bounds for Selection ProblemsJournal of the ACM, 1979
- How good is the information theory bound in sorting?Theoretical Computer Science, 1976