Sorting under partial information (without the ellipsoid algorithm) (Q2439837)

The important paper under review addresses the problem, given a finite partially ordered set \(P\), of finding a linear extension of it using only pairwise comparisons of elements. It is essentially clear, by an entropy argument, that \(\log_2(e(P))\) is a lower bound on the number of comparisons required, where \(e(P)\) is the number of linear extensions of \(P\). The question is whether there is an algorithm, running in polynomial time in the order of \(P\), which will find the linear extension in at most a constant times that lower bound. \textit{J. Kahn} and \textit{J. H. Kim} [in J. Comput. Syst. Sci. 51, No. 3, 390-399 (1995; Zbl 1294.68069)] showed that such an algorithm exists. However it uses the ellipsoid method from optimization which, though in principle polynomial-time, is not very practical. The contribution of the paper under review is to present algorithms which find the linear extension in time polynomial in \(n\) but avoid the use of the ellipsoid method. This is achieved, crudely speaking, by still using the notion of graph entropy but instead of calculating the entropy for arbitrary graphs they show it can be approximated by the entropy of graphs in a restricted class, which means that convex programming and the ellipsoid method can be avoided. To give but one example, the authors present an algorithm running in (where \(n\) is the order of the partially ordered set) time \(O(n^{2.5})\) which uses at most \(15.09\log_2(e(P))\) comparisons; another, with similar running time, uses at most \((1+\varepsilon)\log_2(e(P))+O_\varepsilon(n)\) comparisons, which will be better if \(\log_2(e(P))\) grows faster than \(n\); there are several other algorithms in the paper. Key ideas include greedily decomposing the poset into longest chains and bounding the change in entropy arising from these manoeuvres.