Sorting under partial information (without the ellipsoid algorithm). (Q2439837): Difference between revisions
From MaRDI portal
Changed an Item |
ReferenceBot (talk | contribs) Changed an Item |
||||||||||||||
(2 intermediate revisions by one other user not shown) | |||||||||||||||
aliases / en / 0 | aliases / en / 0 | ||||||||||||||
Sorting under partial information (without the ellipsoid algorithm) | |||||||||||||||
description / en | description / en | ||||||||||||||
scientific article | scientific article; zbMATH DE number 6330075 | ||||||||||||||
Property / title | |||||||||||||||
Sorting under partial information (without the ellipsoid algorithm) (English) | |||||||||||||||
Property / title: Sorting under partial information (without the ellipsoid algorithm) (English) / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / zbMATH Open document ID | |||||||||||||||
Property / zbMATH Open document ID: 1293.68092 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / DOI | |||||||||||||||
Property / DOI: 10.1145/1806689.1806740 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / published in | |||||||||||||||
Property / published in: Proceedings of the forty-second ACM symposium on Theory of computing / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / publication date | |||||||||||||||
13 August 2014
| |||||||||||||||
Property / publication date: 13 August 2014 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / Mathematics Subject Classification ID | |||||||||||||||
Property / Mathematics Subject Classification ID: 68Q25 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / zbMATH DE Number | |||||||||||||||
Property / zbMATH DE Number: 6330075 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / zbMATH Keywords | |||||||||||||||
graph entropy | |||||||||||||||
Property / zbMATH Keywords: graph entropy / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / zbMATH Keywords | |||||||||||||||
partial order | |||||||||||||||
Property / zbMATH Keywords: partial order / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / OpenAlex ID | |||||||||||||||
Property / OpenAlex ID: W2028159002 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Q4821526 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: The number of linear extensions of the Boolean lattice / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Balanced pairs in partial orders / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Balancing pairs and the cross product conjecture / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Counting linear extensions / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Minimum entropy coloring / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: An Efficient Algorithm for Partial Order Production / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Sorting under partial information (without the ellipsoid algorithm). / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Elements of Information Theory / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Entropy splitting for antiblocking corners and perfect graphs / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Q4633848 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Bounds on Optimal Merge Performance, and a Strategy for Optimality / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: How good is the information theory bound in sorting? / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Maximum matching in a convex bipartite graph / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Algorithmic graph theory and perfect graphs / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Fast perfect sampling from linear extensions / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: A Simple Algorithm for Merging Two Disjoint Linearly Ordered Sets / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Entropy and sorting. / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Balancing extensions via Brunn-Minkowski / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Balancing poset extensions / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Q4053473 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Fredman–Komlós bounds and information theory / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Graphs that Split Entropies / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: The Information-Theoretic Bound is Good for Merging / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Normal hypergraphs and the perfect graph conjecture / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Q4840778 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Two poset polytopes / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Graph entropy and quantum sorting problems / rank | |||||||||||||||
Normal rank |
Latest revision as of 12:14, 7 July 2024
scientific article; zbMATH DE number 6330075
- Sorting under partial information (without the ellipsoid algorithm)
Language | Label | Description | Also known as |
---|---|---|---|
English | Sorting under partial information (without the ellipsoid algorithm). |
scientific article; zbMATH DE number 6330075 |
|
Statements
Sorting under partial information (without the ellipsoid algorithm). (English)
0 references
Sorting under partial information (without the ellipsoid algorithm) (English)
0 references
17 March 2014
0 references
13 August 2014
0 references
The important paper under review addresses the problem, given a finite partially ordered set \(P\), of finding a linear extension of it using only pairwise comparisons of elements. It is essentially clear, by an entropy argument, that \(\log_2(e(P))\) is a lower bound on the number of comparisons required, where \(e(P)\) is the number of linear extensions of \(P\). The question is whether there is an algorithm, running in polynomial time in the order of \(P\), which will find the linear extension in at most a constant times that lower bound. \textit{J. Kahn} and \textit{J. H. Kim} [in J. Comput. Syst. Sci. 51, No. 3, 390-399 (1995; Zbl 1294.68069)] showed that such an algorithm exists. However it uses the ellipsoid method from optimization which, though in principle polynomial-time, is not very practical. The contribution of the paper under review is to present algorithms which find the linear extension in time polynomial in \(n\) but avoid the use of the ellipsoid method. This is achieved, crudely speaking, by still using the notion of graph entropy but instead of calculating the entropy for arbitrary graphs they show it can be approximated by the entropy of graphs in a restricted class, which means that convex programming and the ellipsoid method can be avoided. To give but one example, the authors present an algorithm running in (where \(n\) is the order of the partially ordered set) time \(O(n^{2.5})\) which uses at most \(15.09\log_2(e(P))\) comparisons; another, with similar running time, uses at most \((1+\varepsilon)\log_2(e(P))+O_\varepsilon(n)\) comparisons, which will be better if \(\log_2(e(P))\) grows faster than \(n\); there are several other algorithms in the paper. Key ideas include greedily decomposing the poset into longest chains and bounding the change in entropy arising from these manoeuvres.
0 references
finite partially ordered sets
0 references
linear extensions
0 references
polynomial time algorithms
0 references
greedy decompositions of posets
0 references
graph entropy
0 references
partial order
0 references