The Information-Theoretic Bound is Good for Merging
From MaRDI portal
Publication:3340174
DOI10.1137/0213049zbMath0548.68065OpenAlexW2007732780MaRDI QIDQ3340174
Publication date: 1984
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0213049
Related Items (31)
Extensions of the Kahn-Saks inequality for posets of width two ⋮ On linear extensions of ordered sets with a symmetry ⋮ A family of partially ordered sets with small balance constant ⋮ Hard Enumeration Problems in Geometry and Combinatorics ⋮ Computing the number of mergings with constraints ⋮ Linear extensions of infinite posets ⋮ Balancing pairs and the cross product conjecture ⋮ On the optimality of tape merge of two lists with similar size ⋮ The cross-product conjecture for width two posets ⋮ Balance constants for Coxeter groups ⋮ The \(1/3-2/3\) Conjecture for Coxeter groups ⋮ Sorting probability for large Young diagrams ⋮ Sorting under partial information (without the ellipsoid algorithm). ⋮ Greedy balanced pairs in \(N\)-free ordered sets ⋮ The Worst Balanced Partially Ordered Sets—Ladders with Broken Rungs ⋮ Some Completeness Results on Decision Trees and Group Testing ⋮ Antimatroids and balanced pairs ⋮ Balancing extensions via Brunn-Minkowski ⋮ Balance theorems for height-2 posets ⋮ Balancing poset extensions ⋮ The gold partition conjecture ⋮ On the \(1/3-2/3\) conjecture ⋮ Improving the \(\frac{1}{3}\)-\(\frac{2}{3}\) conjecture for width two posets ⋮ Sorting probability of Catalan posets ⋮ Sorting and Selection with Random Costs ⋮ A strange pigeon-hole principle ⋮ The 1/3-2/3 conjecture for ordered sets whose cover graph is a forest ⋮ Semiorders and the 1/3-2/3 conjecture ⋮ On Generalized Comparison-Based Sorting Problems ⋮ Balanced pairs in partial orders ⋮ Every poset has a central element
This page was built for publication: The Information-Theoretic Bound is Good for Merging
