arXiv preprint ·
Improved Integrality Gap for Multicommodity Flow on Trees
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We improve the best known lower bound on the integrality gap for weighted unit-demand multicommodity flow on trees from $1/4$ to $2/5$, improving on the long-standing bound of Chekuri, Mydlarz, and Shepherd~\cite{CMS}. We give the proof in two stages. First, a surprisingly simple packing lemma and an inductive coloring argument give an intermediate bound of $4/11$. We then refine the argument to obtain $2/5$.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Tensor network representations of discrete maximum entropy distributions via mean polytopes
A $(\log n)^{1/4}$ Bound for the Komlós Problem
Entropy bounds and global couplings for union-closed families
The Converse Problem for the Morley Tetrahedron: Counterexamples, Conjectures, and Partial Results
Integer group determinants for the elementary abelian group of order 49
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.