{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:25:50Z","timestamp":1787340350052,"version":"build-2736575974"},"reference-count":30,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"7","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>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 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 partial order. Our approach is to replace the target partial order by a weak order (that is, a partial order with a layered structure) extending it, without increasing the information-theoretic lower bound too much. We then solve the problem by applying an efficient multiple selection algorithm. The overall complexity of our algorithm is polynomial. This answers a question of Yao [SIAM J. Comput., 18 (1989), pp. 679\u2013689]. We base our analysis on the entropy of the target partial order, a quantity that can be efficiently computed and provides a good estimate of the information-theoretic lower bound.<\/jats:p>","DOI":"10.1137\/090759860","type":"journal-article","created":{"date-parts":[[2010,5,5]],"date-time":"2010-05-05T18:08:16Z","timestamp":1273082896000},"page":"2927-2940","source":"Crossref","is-referenced-by-count":6,"title":["An Efficient Algorithm for Partial Order Production"],"prefix":"10.1137","volume":"39","author":[{"given":"Jean","family":"Cardinal","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Samuel","family":"Fiorini","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gwena\u00ebl","family":"Joret","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rapha\u00ebl M.","family":"Jungers","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"J. Ian","family":"Munro","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2010,5,5]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(81)90197-7"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"B. Bollob\u00e1s and P. Hell,\n                      Sorting and graphs\n                      , in Graphs and Order (Banff, Alta., 1984), NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci. 147, Reidel, Dordrecht, The Netherlands, 1985, pp. 169\u2013184.","DOI":"10.1007\/978-94-009-5315-4_5"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1007\/BF00383444"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9076-8"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"J. Cardinal, S. Fiorini, G. Joret, R. M. Jungers, and J. I. Munro,\n                      An efficient algorithm for partial order production\n                      , in Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC '09), Bethesda, MD, 2009, pp. 93\u2013100.","DOI":"10.1145\/1536414.1536430"},{"key":"R6","unstructured":"S. Carlsson and J. Chen,\n                      The complexity of heaps\n                      , in Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '92), Orlando, FL, 1992, pp. 393\u2013402."},{"key":"R7","doi-asserted-by":"crossref","unstructured":"S. Carlsson and J. Chen,\n                      Some lower bounds for comparison-based algorithms\n                      , in Proceedings of the 2nd European Symposium on Algorithms (ESA '94), Utrecht, The Netherlands, Lecture Notes in Comput. Sci. 855, Springer-Verlag, Berlin, 1994, pp. 106\u2013117.","DOI":"10.1007\/BFb0049401"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1145\/362588.362602"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"J. Chen,\n                      Average cost to produce partial orders\n                      , in Proceedings of the 5th International Symposium on Algorithms and Computation (ISAAC '94), Beijing, People's Republic of China, Lecture Notes in Comput. Sci. 834, Springer-Verlag, Berlin, 1994, pp. 155\u2013163.","DOI":"10.1007\/3-540-58325-4_177"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(75)90041-6"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1007\/BF02122693"},{"key":"R12","unstructured":"J. C. Culberson and G. J. E. Rawlins,\n                      On the Comparison Cost of Partial Orders\n                      , Technical report TR88-01, Department of Computing Science, University of Alberta, Edmonton, Alberta, Canada, 1988."},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1145\/322261.322264"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"M. L. Fredman,\n                      How good is the information theory bound in sorting?\n                      , Theoret. Comput. Sci., 1 (1975\/76), pp. 355\u2013361.","DOI":"10.1016\/0304-3975(76)90078-5"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"M. C. Golumbic,\n                      Algorithmic Graph Theory and Perfect Graphs\n                      , 2nd ed., Ann. Discrete Math. 57, Elsevier, Amsterdam, 2004.","DOI":"10.1016\/S0167-5060(04)80051-7"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"M. Gr\u00f6tschel, L. Lov\u00e1sz, and A. Schrijver,\n                      Geometric Algorithms and Combinatorial Optimization\n                      , 2nd ed., Algorithms Combin. 2, Springer-Verlag, Berlin, 1993.","DOI":"10.1007\/978-3-642-78240-4"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1145\/366622.366644"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1077"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1007\/BF00565647"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"K. Kaligosi, K. Mehlhorn, J. I. Munro, and P. Sanders,\n                      Towards optimal multiple selection\n                      , in Proceedings of the International Conference on Automata, Languages, and Programming (ICALP '05), Lecture Notes in Comput. Sci. 3580, Springer-Verlag, Berlin, 2005, pp. 103\u2013114.","DOI":"10.1007\/11523468_9"},{"key":"R21","unstructured":"J. K\u00f6rner,\n                      Coding of an information source having ambiguous alphabet and the entropy of graphs\n                      , in Transactions of the Sixth Prague Conference on Information Theory, Academia, Prague, Czech Republic, 1973, pp. 411\u2013425."},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1137\/0213049"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(72)90006-4"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"Y. Nesterov and A. Nemirovskii,\n                      Interior-Point Polynomial Algorithms in Convex Programming\n                      , SIAM Stud. Appl. Math. 13, SIAM, Philadelphia, 1994.","DOI":"10.1137\/1.9781611970791"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00729-6"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(95)00150-B"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"M. E. Saks,\n                      The information theoretic bound for problems on ordered sets and graphs\n                      , in Graphs and Order (Banff, Alta., 1984), NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci. 147, Reidel, Dordrecht, The Netherlands, 1985, pp. 137\u2013168.","DOI":"10.1007\/978-94-009-5315-4_4"},{"key":"R28","first-page":"229","volume":"38","author":"Sch\u00f6nhage A.","year":"1976","journal-title":"Ast\u00e9risque","ISSN":"https:\/\/id.crossref.org\/issn\/0303-1179","issn-type":"print"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187680"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1137\/0218047"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/090759860","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:31:30Z","timestamp":1787337090000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/090759860"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":30,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/090759860"],"URL":"https:\/\/doi.org\/10.1137\/090759860","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]}}}