An Efficient Algorithm for Partial Order Production
(2010) SIAM Journal on Computing — Vol. 39, n° 7, p. 2927-2940 (2010)
Files
pop_jungers.pdf
Restricted Access - Adobe PDF
- 252.86 KB
Details
- Authors
- 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 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 partial order. Our approach is to replace the target partial order by a weak order (that is, a partial order with a layered structure) extending it, without increasing the information-theoretic lower bound too much. We then solve the problem by applying an efficient multiple selection algorithm. The overall complexity of our algorithm is polynomial. This answers a question of Yao [SIAM J. Comput., 18 (1989), pp. 679-689]. We base our analysis on 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.
- Affiliations
Citations
Cardinal, J., Fiorini, S., Joret, G., Jungers, R., & Munro, J. I. (2010). An Efficient Algorithm for Partial Order Production. SIAM Journal on Computing, 39(7), 2927-2940. https://doi.org/10.1137/090759860 (Original work published 2010)