Jeff Kahn
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 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 Ω(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 nn/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.
- 1.R. Boppana, Optimal separations between concurrent-write parallel machines, Proc. 21s# Annual A CM Symposium on Theory of Computing (1989), 320-326. Google Scholar
Digital Library
- 2.H. Buseman, C'onvez Surfaces, Interscience, New York, 1985.Google Scholar
- 3.V. Chv#tal, On certain poly#opes associated with graphs, J. Combinatorial Th. B 18 (1975), 138-154.Google ScholarCross Ref
- 4.I. Csisz#r, J. K6rner, L. Lov#z, K. Marton and G. Simonyi, Entropy splitting for antiblocking corners and perfect graphs, Combinatorica 10 (1990), 27-40.Google ScholarCross Ref
- 5.R.P. Dilworth, Some combinatorial problems on partially ordered sets, Proc. AM3 Symposia in Appl. Math 10 (1960), 85-90.Google Scholar
- 6.M.E. Dyer, A.M. Frieze and R. Kannan, A random polynomial time algorithm for approximating the volume of convex bodies, Proc. #lst Annual A GM Symposium on Theory of Computing (1989), 375-381. Google ScholarDigital Library
- 7.M.L. Fredman, How good is the information theory bound in sorting?, Theoretical Computer Science I (1976), 355-361.Google ScholarCross Ref
- 8.J. Friedman, A note on poser geometries,Google Scholar
- 9.D.P#. Fulkerson, On the perfect graph theorem, pp. 69-77 in Mathematical Programming (T.C. Hu and S.M. Robinson, eds.), Academic Press, New York, 1973.Google Scholar
- 10.M. GrStschel, L. Lovgmz and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Springer-Verlag, 1988.Google Scholar
- 11.J. Kahn and N. Linial, Balancing extensions via Brunn-Minkowski, Gombinatorica 11 (1991), 363-368.Google ScholarCross Ref
- 12.J. Kahn and M. Saks, Balancing poser extensions, Order I (1984), 113-126.Google ScholarCross Ref
- 13.A. Karzanov and L. Khachiyan, On the conductance of order Markov chains, Order 8 (1991), 7-15.Google ScholarCross Ref
- 14.L. Khachiyan, Optimal algorithms in convex programming, decomposition and sorting, in Computers and Decision Problems (Ju. Jaravlev, ed.) Moscow, Nauka, 1989, pp. 161-205 (Russian).Google Scholar
- 15.J. Koml6s, A strange pigeon-hole principle, Order 7 (1990), 107-113.Google ScholarCross Ref
- 16.J. KSrner, Coding of an information source having ambiguous alphabet and the entropy of graphs, Trans. 6th Prague Conf. information Th. etc. (1973) 411-425Google Scholar
- 17.J. KSrner, Fredman-Koml6s bounds and information theory, SIAM Y. Alg. Disc. Meth. 7 (1986), 560-570. Google ScholarDigital Library
- 18.J. KSrner and K. Matron, New bounds for perfect hashing via information theory, Europ. J. Combinatorics Google ScholarDigital Library
- 19.L. Lov#z and M. Simonovits, The mixing rate of Markov chains, an isoperimetric inequality, and computing the volume, Pvoc. 31st IF, EE S#tmp. Found. Gomp. Sci. (1990), 346-355.Google Scholar
- 20.N. Linial, The information theoretic bound is good for merging, SIAM J. Computing 13 (1984), 795-801.Google ScholarCross Ref
- 21.R.P. Stanley, Two poser polytopes, Discrete and Computational Geom. 1 (1986), 9-23. Google ScholarDigital Library
- 22.W.T. Trotter, Problems and conjectures in the combinatorial theory of ordered sets, Ann. Discrete. Math. 41 (1989), 401-416.Google ScholarCross Ref
Index Terms
- Entropy and sorting
Recommendations
Sorting in Linear Time?
We show that a unit-cost RAM with a word length ofwbits can sortnintegers in the range 0 2w 1 inO(nloglogn) time for arbitraryw logn, a significant improvement over the bound ofO(nlogn) achieved by the fusion trees of Fredman and Willard. Provided thatw ...
Equivalence between priority queues and sorting
We present a general deterministic linear space reduction from priority queues to sorting implying that if we can sort up to n keys in S(n) time per key, then there is a priority queue supporting delete and insert in O(S(n)) time and find-min in ...
Probabilistic integer sorting
We introduce a probabilistic sequential algorithm for stable sorting n uniformly distributed keys in an arbitrary range. The algorithm runs in linear time and sorts all but a very small fraction 2-Ω(n) of the input sequences; the best previously known ...
Comments