An efficient algorithm for partial order production

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).

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.

REFERENCES

• 1: M. Aigner. Producing posets. Discrete Math., 35:1--15, 1981.
• 2: B. Bollobas and P. Hell. Sorting and graphs. In Graphs and order, Banff, Alta., 1984, volume 147 of NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., pages 169--184, Dordrecht, 1985. Reidel.
• 3: Jean Cardinal , Samuel Fiorini , Gwenaël Joret, Tight Results on Minimum Entropy Set Cover, Algorithmica, v.51 n.1, p.49-60, March 2008 [doi>10.1007/s00453-007-9076-8]
• 4: Svante Carlsson , Jingsen Chen, The complexity of heaps, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.393-402, September 1992, Orlando, Florida, United States
• 5: Svante Carlsson , Jingsen Chen, Some Lower Bounds for Comparison-Based Algorithms, Proceedings of the Second Annual European Symposium on Algorithms, p.106-117, September 26-28, 1994
• 6: J. M. Chambers, Algorithm 410: Partial sorting, Communications of the ACM, v.14 n.5, p.357-358, May 1971 [doi>10.1145/362588.362602]
• 7: J. Chen. Average cost to produce partial orders. In D. Du and X. Zhang, editors, Proc. 5th International Symposium on Algorithms and Computation (ISAAC '94), Beijing, P. R. China, August 25--27, 1994, volume 834 of Lecture Notes in Computer Science, pages 155--163. Springer, 1994.
• 8: V. Chvatal. On certain polytopes associated with graphs. J. Combinatorial Theory Ser. B, 18:138--154, 1975.
• 9: I. Csiszar, J. Korner, L. Lovasz, K. Marton, and G. Simonyi. Entropy splitting for antiblocking corners and perfect graphs. Combinatorica, 10(1):27--40, 1990.
• 10: J.C. Culberson and G.J.E. Rawlins. On the comparison cost of partial orders. Technical Report TR88-01, Department of Computing Science, University of Alberta, Edmonton, Alberta, Canada T6G 2E8, 1988.
• 11: David Dobkin , J. Ian Munro, Optimal Time Minimal Space Selection Algorithms, Journal of the ACM (JACM), v.28 n.3, p.454-461, July 1981 [doi>10.1145/322261.322264]
• 12: M. L. Fredman. How good is the information theory bound in sorting? Theor. Comput. Sci., 1(4):355--361, 1976.
• 13: C. A. R. Hoare. Find (algorithm 65). Commun. ACM, 4(7):321--322, 1961.
• 14: Jeff Kahn , Jeong Han Kim, Entropy and sorting, Journal of Computer and System Sciences, v.51 n.3, p.390-399, Dec. 1995 [doi>10.1006/jcss.1995.1077]
• 15: J. Kahn and M. E. Saks. Balancing poset extensions. Order, 1:113--126, 1984.
• 16: K. Kaligosi, K. Mehlhorn, J. I. Munro, and P. Sanders. Towards optimal multiple selection. In Proc. International Conference on Automata, Languages, and Programming (ICALP'05), Lecture Notes in Computer Science, pages 103--114. Springer--Verlag, 2005.
• 17: J. Korner. Coding of an information source having ambiguous alphabet and the entropy of graphs. In Transactions of the 6th Prague Conference on Information Theory, pages 411--425, 1973.
• 18: N. Linial. The information-theoretic bound is good for merging. SIAM J. Comput., 13(4):795--801, 1984.
• 19: L. Lovasz. Normal hypergraphs and the perfect graph conjecture. Discrete Math., 2(3):253--267, 1972.
• 20: Y. Nesterov and A. Nemirovskii. Interior-point polynomial algorithms in convex programming, volume 13 of SIAM Studies in Applied Mathematics. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1994.
• 21: Alois Panholzer, Analysis of multiple quickselect variants, Theoretical Computer Science, v.302 n.1-3, p.45-91, 13 June 2003 [doi>10.1016/S0304-3975(02)00729-6]
• 22: Helmut Prodinger, Multiple Quickselect—Hoare's Find algorithm for several elements, Information Processing Letters, v.56 n.3, p.123-129, Nov. 10, 1995 [doi>10.1016/0020-0190(95)00150-B]
• 23: M. E. Saks. The information theoretic bound for problems on ordered sets and graphs. In Graphs and order, Banff, Alta., 1984, volume 147 of NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., pages 137--168, Dordrecht, 1985. Reidel.
• 24: A. Schonhage. The production of partial orders. In Journees algorithmiques, Ecole Norm. Sup., Paris, 1975, pages 229--246. Asterisque, No. 38--39. Soc. Math. France, Paris, 1976.
• 25: Richard P. Stanley, Two poset polytopes, Discrete & Computational Geometry, v.1 n.1, p.9-23, 1986 [doi>10.1007/BF02187680]
• 26: Andrew Chi-Chih Yao, On the complexity of partial order productions, SIAM Journal on Computing, v.18 n.4, p.679-689, Aug. 1989 [doi>10.1137/0218047]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Theory

Keywords:
graph entropy, partial order