An Efficient Algorithm for Partial Order Production

by Gwenael Joret

Institution: Departement d'Informatique, Universite Libre de Bruxelles
Date: Tue 16th June 2009
Time: 2:15 PM
Location: Room 107, Richard Berry Building, The University of Melbourne

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.