User menu

Sorting under Partial Information (without the Ellipsoid Algorithm)

Bibliographic reference Cardinal, Jean ; Fiorini, Samuel ; Joret, Gwenael ; Jungers, Raphaël M. ; Munro, J.Ian. Sorting under Partial Information (without the Ellipsoid Algorithm). In: Combinatorica - an international journal of the János Bolyai Mathematical Society, Vol. 33, no. 6, p. 655-697 (2013)
Permanent URL
  1. Boyd Stephen, Vandenberghe Lieven, Convex Optimization, ISBN:9780511804441, 10.1017/cbo9780511804441
  2. Brightwell Graham R., Tetali Prasad, The Number of Linear Extensions of the Boolean Lattice, 10.1023/b:orde.0000034596.50352.f7
  3. Brightwell Graham, Balanced pairs in partial orders, 10.1016/s0012-365x(98)00311-2
  4. Brightwell G. R., Felsner S., Trotter W. T., Balancing pairs and the cross product conjecture, 10.1007/bf01110378
  5. Brightwell Graham, Winkler Peter, Counting linear extensions, 10.1007/bf00383444
  6. Cardinal Jean, Fiorini Samuel, Joret Gwenaël, Minimum entropy coloring, 10.1007/s10878-008-9152-2
  7. Cardinal Jean, Fiorini Samuel, Joret Gwenaël, Jungers Raphaël M., Munro J. Ian, An Efficient Algorithm for Partial Order Production, 10.1137/090759860
  8. Cardinal Jean, Fiorini Samuel, Joret Gwenaël, Jungers Raphaël M., Munro J. Ian, Sorting under partial information (without the ellipsoid algorithm), 10.1145/1806689.1806740
  9. T. M. Cover and J. A. Thomas: Elements of Information Theory, 2nd Edition, Wiley, 2006.
  10. Csiszár I., Körner J., Lovász L., Marton K., Simonyi G., Entropy splitting for antiblocking corners and perfect graphs, 10.1007/bf02122693
  11. Daskalakis Constantinos, Karp Richard M., Mossel Elchanan, Riesenfeld Samantha, Verbin Elad, Sorting and Selection in Posets, Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (2009) ISBN:9780898716801 p.392-401, 10.1137/1.9781611973068.44
  12. Frazer W. D., Bennett B. T., Bounds on Optimal Merge Performance, and a Strategy for Optimality, 10.1145/321724.321729
  13. Fredman Michael L., How good is the information theory bound in sorting?, 10.1016/0304-3975(76)90078-5
  14. Glover Fred, Maximum matching in a convex bipartite graph, 10.1002/nav.3800140304
  15. M. C. Golumbic: Algorithmic Graph Theory and Perfect Graphs, 2nd edition, Annals of Discrete Mathematics, Elsevier, 2004.
  16. Huber Mark, Fast perfect sampling from linear extensions, 10.1016/j.disc.2006.01.003
  17. Hwang F. K., Lin S., A Simple Algorithm for Merging Two Disjoint Linearly Ordered Sets, 10.1137/0201004
  18. Kahn J., Kim J.H., Entropy and Sorting, 10.1006/jcss.1995.1077
  19. Kahn Jeff, Linial Nathan, Balancing extensions via Brunn-Minkowski, 10.1007/bf01275670
  20. Kahn Jeff, Saks Michael, Balancing poset extensions, 10.1007/bf00565647
  21. J. Körner: Coding of an information source having ambiguous alphabet and the entropy of graphs, In: Transactions of the 6th Prague Conference on Information Theory, 411–425, 1973.
  22. Körner Jénos, Fredman–Komlós bounds and information theory, 10.1137/0607062
  23. Körner J., Marton K., Graphs that Split Entropies, 10.1137/0401008
  24. Linial Nathan, The Information-Theoretic Bound is Good for Merging, 10.1137/0213049
  25. Lovász L., Normal hypergraphs and the perfect graph conjecture, 10.1016/0012-365x(72)90006-4
  26. G. Simonyi: Graph entropy: a survey, In: Combinatorial optimization (New Brunswick, NJ, 1992–1993), volume 20 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 399–441. Amer. Math. Soc., Providence, RI, 1995.
  27. Stanley Richard P., Two poset polytopes, 10.1007/bf02187680
  28. A. C.-C. Yao: Graph entropy and quantum sorting problems, In: STOC’04: 36th Annual ACM Symposium on Theory of Computing, 112–117, 2004.