Sorting under partial information (without the ellipsoid algorithm).

DOI10.1007/s00493-013-2821-5zbMath1315.06002arXiv0911.0086OpenAlexW2611100310MaRDI QIDQ2439837

J. Ian Munro, Jean Cardinal, Samuel Fiorini, Raphaël M. Jungers, Gwenaël Joret

Publication date: 17 March 2014

Published in: Combinatorica, Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0911.0086

zbMATH Keywords

partial ordergraph entropypolynomial time algorithmsfinite partially ordered setslinear extensionsgreedy decompositions of posets

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Nonnumerical algorithms (68W05) Combinatorics of partially ordered sets (06A07) Measures of information, entropy (94A17)

Related Items

Sorting probability for large Young diagrams, Sorting under partial information (without the ellipsoid algorithm)., A practical perspective on knowledge space theory: ALEKS and its data, Asymptotics of the number of standard Young tableaux of skew shape, Linear extensions and comparable pairs in partial orders, Improving the \(\frac{1}{3}\)-\(\frac{2}{3}\) conjecture for width two posets, Poset entropy versus number of linear extensions: the width-2 case., Preprocessing Ambiguous Imprecise Points, On Generalized Comparison-Based Sorting Problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Entropy splitting for antiblocking corners and perfect graphs
• Entropy and sorting.
• Minimum entropy coloring
• Two poset polytopes
• Balancing extensions via Brunn-Minkowski
• Counting linear extensions
• How good is the information theory bound in sorting?
• Balanced pairs in partial orders
• The number of linear extensions of the Boolean lattice
• Algorithmic graph theory and perfect graphs
• Balancing pairs and the cross product conjecture
• Balancing poset extensions
• Fast perfect sampling from linear extensions
• Sorting under partial information (without the ellipsoid algorithm).
• Normal hypergraphs and the perfect graph conjecture
• Graphs that Split Entropies
• The Information-Theoretic Bound is Good for Merging
• Graph entropy and quantum sorting problems
• Fredman–Komlós bounds and information theory
• An Efficient Algorithm for Partial Order Production
• Elements of Information Theory
• Maximum matching in a convex bipartite graph
• A Simple Algorithm for Merging Two Disjoint Linearly Ordered Sets
• Bounds on Optimal Merge Performance, and a Strategy for Optimality