Entropy and Sorting Seminars/Workshops

Abstract

We reconsider the old problem of sorting under partial information, and give polynomial time algorithms for the following tasks.

(1) Given a partial order $P$, find (adaptively) a sequence of comparisons (questions of the form, ``is $x<y$?") which {\em sorts} (i.e. finds an unknown linear extension of) $P$ using $O(\log(e(P)))$ comparisons in worst case (where $e(P)$ is the number of linear extensions of $P$).

(2) Compute (on line) answers to any comparison algorithm for sorting a partial order $P$ which force the algorithm to use $\Omega(\log(e(P)))$ comparisons.

(3) Given a partial order $P$ of size $n$, estimate $e(P)$ to within a factor exponential in $n$. (We give upper and lower bounds which differ by the factor $n^n/n!$.)

Our approach, based on entropy of the comparability graph of $P$ and convex minimization via the ellipsoid method, is completely different from earlier attempts to deal with these questions.