Computer Science – Data Structures and Algorithms
Scientific paper
2008-11-17
SIAM J. Comput. Volume 39, Issue 7, pp. 2927-2940 (2010)
Computer Science
Data Structures and Algorithms
Referees' comments incorporated
Scientific paper
10.1137/090759860
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). 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.
Cardinal Jean
Fiorini Samuel
Joret Gwenaël
Jungers Raphael M.
Munro Ian J.
No associations
LandOfFree
An Efficient Algorithm for Partial Order Production does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with An Efficient Algorithm for Partial Order Production, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Efficient Algorithm for Partial Order Production will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-466268