Cardinal, Jean
Fiorini, Samuel
Joret, Gwenael
Jungers, Raphaël M.
[UCL]
Munro, J. Ian
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.
Bibliographic reference |
Cardinal, Jean ; Fiorini, Samuel ; Joret, Gwenael ; Jungers, Raphaël M. ; Munro, J. Ian. An Efficient Algorithm for Partial Order Production. In: SIAM Journal on Computing, Vol. 39, no. 7, p. 2927-2940 (2010) |
Permanent URL |
http://hdl.handle.net/2078.1/33598 |