{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,20]],"date-time":"2025-09-20T18:23:24Z","timestamp":1758392604220},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2013,12,1]],"date-time":"2013-12-01T00:00:00Z","timestamp":1385856000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2013,12]]},"DOI":"10.1007\/s00493-013-2821-5","type":"journal-article","created":{"date-parts":[[2014,1,15]],"date-time":"2014-01-15T06:40:09Z","timestamp":1389768009000},"page":"655-697","source":"Crossref","is-referenced-by-count":6,"title":["Sorting under partial information (without the ellipsoid algorithm)"],"prefix":"10.1007","volume":"33","author":[{"given":"Jean","family":"Cardinal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Samuel","family":"Fiorini","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gwena\u00ebl","family":"Joret","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rapha\u00ebl M.","family":"Jungers","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J. Ian","family":"Munro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,1,16]]},"reference":[{"key":"2821_CR1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804441","volume-title":"Convex optimization","author":"S Boyd","year":"2004","unstructured":"S. Boyd and L. Vandenberghe: Convex optimization, Cambridge University Press, Cambridge, 2004."},{"key":"2821_CR2","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1023\/B:ORDE.0000034596.50352.f7","volume":"20","author":"G Brightwell","year":"2003","unstructured":"G. Brightwell and P. Tetali: The number of linear extensions of the boolean lattice. Order 20 (2003), 333\u2013345.","journal-title":"Order"},{"key":"2821_CR3","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/S0012-365X(98)00311-2","volume":"201","author":"G R Brightwell","year":"1999","unstructured":"G. R. Brightwell: Balanced pairs in partial orders, Discrete Mathematics 201 (1999), 25\u201352.","journal-title":"Discrete Mathematics"},{"key":"2821_CR4","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1007\/BF01110378","volume":"2","author":"G R Brightwell","year":"1995","unstructured":"G. R. Brightwell, S. Felsner and W. T. Trotter: Balancing pairs and the cross product conjecture, Order 2 (1995), 327\u2013349.","journal-title":"Order"},{"key":"2821_CR5","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1007\/BF00383444","volume":"8","author":"G R Brightwell","year":"1991","unstructured":"G. R. Brightwell and P. Winkler: Counting linear extensions, Order 8 (1991), 225\u2013242.","journal-title":"Order"},{"key":"2821_CR6","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1007\/s10878-008-9152-2","volume":"16","author":"J Cardinal","year":"2008","unstructured":"J. Cardinal, S. Fiorini and G. Joret: Minimum entropy coloring, J. Comb. Opt. 16 (2008), 361\u2013377.","journal-title":"J. Comb. Opt."},{"key":"2821_CR7","doi-asserted-by":"crossref","first-page":"2927","DOI":"10.1137\/090759860","volume":"39","author":"J Cardinal","year":"2010","unstructured":"J. Cardinal, S. Fiorini, G. Joret, R. M. Jungers and J. I. Munro: An efficient algorithm for partial order production, SIAM J. Comput. 39 (2010), 2927\u20132940.","journal-title":"SIAM J. Comput."},{"key":"2821_CR8","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1145\/1806689.1806740","volume-title":"STOC\u2019 10: Proceedings of the 42nd ACM symposium on Theory of computing","author":"J Cardinal","year":"2010","unstructured":"J. Cardinal, S. Fiorini, G. Joret, R. M. Jungers and J. I. Munro: Sorting under partial information (without the ellipsoid algorithm), In: STOC\u2019 10: Proceedings of the 42nd ACM symposium on Theory of computing, 359\u2013368, New York, NY, USA, 2010."},{"key":"2821_CR9","volume-title":"Elements of Information Theory","author":"T M Cover","year":"2006","unstructured":"T. M. Cover and J. A. Thomas: Elements of Information Theory, 2nd Edition, Wiley, 2006.","edition":"2nd Edition"},{"key":"2821_CR10","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1007\/BF02122693","volume":"10","author":"I Csisz\u00e1r","year":"1990","unstructured":"I. Csisz\u00e1r, J. K\u00f6rner, L. Lov\u00e1sz, K. Marton and G. Simonyi: Entropy splitting for antiblocking corners and perfect graphs, Combinatorica 10 (1990), 27\u201340.","journal-title":"Combinatorica"},{"key":"2821_CR11","doi-asserted-by":"crossref","first-page":"392","DOI":"10.1137\/1.9781611973068.44","volume-title":"Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201909)","author":"C Daskalakis","year":"2009","unstructured":"C. Daskalakis, R. M. Karp, E. Mossel, S. Riesenfeld and E. Verbin: Sorting and selection in posets, In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201909), 392\u2013401, 2009."},{"key":"2821_CR12","doi-asserted-by":"crossref","first-page":"641","DOI":"10.1145\/321724.321729","volume":"19","author":"W D Frazer","year":"1972","unstructured":"W. D. Frazer and B. T. Bennett: Bounds on optimal merge performance, and a strategy for optimality, J. ACM 19 (1972), 641\u2013648.","journal-title":"J. ACM"},{"key":"2821_CR13","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1016\/0304-3975(76)90078-5","volume":"1","author":"M L Fredman","year":"1976","unstructured":"M. L. Fredman: How good is the information theory bound in sorting? Theor. Comput. Sci. 1 (1976), 355\u2013361.","journal-title":"Theor. Comput. Sci."},{"key":"2821_CR14","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1002\/nav.3800140304","volume":"4","author":"F Glover","year":"1967","unstructured":"F. Glover: Maximum matchings in a convex bipartite graph, Naval Research Logistics Quarterly 4 (1967), 313\u2013316.","journal-title":"Naval Research Logistics Quarterly"},{"key":"2821_CR15","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M C Golumbic","year":"2004","unstructured":"M. C. Golumbic: Algorithmic Graph Theory and Perfect Graphs, 2nd edition, Annals of Discrete Mathematics, Elsevier, 2004.","edition":"2nd edition"},{"key":"2821_CR16","doi-asserted-by":"crossref","first-page":"420","DOI":"10.1016\/j.disc.2006.01.003","volume":"306","author":"M Huber","year":"2006","unstructured":"M. Huber: Fast perfect sampling from linear extensions, Discrete Mathematics 306 (2006), 420\u2013428.","journal-title":"Discrete Mathematics"},{"key":"2821_CR17","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1137\/0201004","volume":"1","author":"F K Hwang","year":"1972","unstructured":"F. K. Hwang and S. Lin: A simple algorithm for merging two disjoint linearly-ordered sets. SIAM J. Comput. 1 (1972), 31\u201339.","journal-title":"SIAM J. Comput."},{"key":"2821_CR18","doi-asserted-by":"crossref","first-page":"390","DOI":"10.1006\/jcss.1995.1077","volume":"51","author":"J Kahn","year":"1995","unstructured":"J. Kahn and J. H. Kim: Entropy and sorting, J. Comput. Syst. Sci. 51 (1995), 390\u2013399.","journal-title":"J. Comput. Syst. Sci."},{"key":"2821_CR19","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1007\/BF01275670","volume":"11","author":"J Kahn","year":"1991","unstructured":"J. Kahn and N. Linial: Balancing extensions via Brunn-Minkowski, Combinatorica 11 (1991), 363\u2013368.","journal-title":"Combinatorica"},{"key":"2821_CR20","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1007\/BF00565647","volume":"1","author":"J Kahn","year":"1984","unstructured":"J. Kahn and M. E. Saks: Balancing poset extensions, Order 1 (1984), 113\u2013126.","journal-title":"Order"},{"key":"2821_CR21","first-page":"411","volume-title":"Transactions of the 6th Prague Conference on Information Theory","author":"J K\u00f6rner","year":"1973","unstructured":"J. K\u00f6rner: Coding of an information source having ambiguous alphabet and the entropy of graphs, In: Transactions of the 6th Prague Conference on Information Theory, 411\u2013425, 1973."},{"key":"2821_CR22","doi-asserted-by":"crossref","first-page":"560","DOI":"10.1137\/0607062","volume":"7","author":"J K\u00f6rner","year":"1986","unstructured":"J. K\u00f6rner: Fredman-Koml\u00f3s bounds and information theory, SIAM J. Algebraic Discrete Methods 7 (1986), 560\u2013570.","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"2821_CR23","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1137\/0401008","volume":"1","author":"J K\u00f6rner","year":"1998","unstructured":"J. K\u00f6rner and K. Marton: Graphs that split entropies, SIAM J. Discrete Math. 1 (1998), 71\u201379.","journal-title":"SIAM J. Discrete Math."},{"key":"2821_CR24","doi-asserted-by":"crossref","first-page":"795","DOI":"10.1137\/0213049","volume":"13","author":"N Linial","year":"1984","unstructured":"N. Linial: The information-theoretic bound is good for merging, SIAM J. Comput. 13 (1984), 795\u2013801.","journal-title":"SIAM J. Comput."},{"key":"2821_CR25","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1016\/0012-365X(72)90006-4","volume":"2","author":"L Lov\u00e1sz","year":"1972","unstructured":"L. Lov\u00e1sz: Normal hypergraphs and the perfect graph conjecture, Discrete Math. 2 (1972), 253\u2013267.","journal-title":"Discrete Math."},{"key":"2821_CR26","series-title":"DIMACS Ser. Discrete Math. Theoret. Comput. Sci.","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1090\/dimacs\/020\/08","volume-title":"Combinatorial optimization (New Brunswick, NJ, 1992\u20131993)","author":"G Simonyi","year":"1995","unstructured":"G. Simonyi: Graph entropy: a survey, In: Combinatorial optimization (New Brunswick, NJ, 1992\u20131993), volume 20 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 399\u2013441. Amer. Math. Soc., Providence, RI, 1995."},{"key":"2821_CR27","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1007\/BF02187680","volume":"1","author":"R P Stanley","year":"1986","unstructured":"R. P. Stanley: Two poset polytopes, Discrete Comput. Geom. 1 (1986), 9\u201323.","journal-title":"Discrete Comput. Geom."},{"key":"2821_CR28","first-page":"112","volume-title":"STOC\u201904: 36th Annual ACM Symposium on Theory of Computing","author":"A C-C Yao","year":"2004","unstructured":"A. C.-C. Yao: Graph entropy and quantum sorting problems, In: STOC\u201904: 36th Annual ACM Symposium on Theory of Computing, 112\u2013117, 2004."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-013-2821-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-013-2821-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-013-2821-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T15:12:40Z","timestamp":1565104360000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-013-2821-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,12]]},"references-count":28,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2013,12]]}},"alternative-id":["2821"],"URL":"https:\/\/doi.org\/10.1007\/s00493-013-2821-5","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,12]]}}}