The Information-Theoretic Bound is Good for Merging
From MaRDI portal
Publication:3340174
DOI10.1137/0213049zbMATH Open0548.68065OpenAlexW2007732780MaRDI QIDQ3340174FDOQ3340174
Authors: Nathan Linial 
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
Cited In (30)
- The \(1/3-2/3\) Conjecture for Coxeter groups
- Greedy balanced pairs in \(N\)-free ordered sets
- Hard Enumeration Problems in Geometry and Combinatorics
- The cross-product conjecture for width two posets
- A strange pigeon-hole principle
- Balancing poset extensions
- Computing the number of mergings with constraints
- Balanced pairs in partial orders
- A family of partially ordered sets with small balance constant
- Some Completeness Results on Decision Trees and Group Testing
- The gold partition conjecture
- Sorting and Selection with Random Costs
- Balance constants for Coxeter groups
- Extensions of the Kahn-Saks inequality for posets of width two
- The worst balanced partially ordered sets-ladders with broken rungs
- Sorting probability for large Young diagrams
- Improving the \(\frac{1}{3}\)-\(\frac{2}{3}\) conjecture for width two posets
- Every poset has a central element
- Sorting probability of Catalan posets
- The 1/3-2/3 conjecture for ordered sets whose cover graph is a forest
- Antimatroids and balanced pairs
- On linear extensions of ordered sets with a symmetry
- Balancing extensions via Brunn-Minkowski
- On generalized comparison-based sorting problems
- On the optimality of tape merge of two lists with similar size
- On the \(1/3-2/3\) conjecture
- Linear extensions of infinite posets
- Balance theorems for height-2 posets
- Balancing pairs and the cross product conjecture
- Semiorders and the 1/3-2/3 conjecture
This page was built for publication: The Information-Theoretic Bound is Good for Merging
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3340174)
