An Efficient Algorithm for Partial Order Production
by Gwenael Joret
Abstract: We consider the problem of partial order production: arrange the elements of an unknown totally ordered set T into a target partially ordered set S, by comparing a minimum number of pairs in T. Special cases of this problem include sorting by comparisons, selection, multiple selection, and heap construction. We give an algorithm performing ITLB + o(ITLB) + O(n) comparisons in the worst case. Here, n denotes the size of the ground sets, and ITLB denotes a natural information-theoretic lower bound on the number of comparisons needed to produce the target poset. The overall complexity of our algorithm is polynomial. This answers a question of Yao (SICOMP, 1989). A key ingredient in our analysis is the entropy of the target partial order, a quantity that can be efficiently computed and provides a good estimate of the information-theoretic lower bound. Joint work with J. Cardinal, S. Fiorini, R. M. Jungers, and I. Munro.
For More Information: contact: David Wood, email : email@example.com