Universität zu Köln
Mathematisch-Naturwissenschaftliche Fakultät
Arbeitsgruppe Faigle/Schrader
Dr. Samuel Fiorini,
Université Libre de Bruxelles
Département de Mathématique
An Efficient Algorithm for Partial Order Production
We consider the problem of partial order production:
arrange the elements of an unknown totally ordered 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).
Our strategy is to extend the poset S to a weak order W whose
corresponding information-theoretic lower bound is provably not much
larger than that for S. Taking W instead of S as a target poset, we
then solve the problem by applying a multiple selection algorithm
that performs not much more than ITLB comparisons.
We base our analysis on the entropy of the target poset S, a quantity
that can be efficiently computed and provides a good estimate of ITLB
since the latter is, up to a linear error term, n times the entropy
of S.
This is joint work with Jean Cardinal (ULB), Gwenaël Joret (ULB),
Raphaël M. Jungers (UCL), Ian Munro (Waterloo)