Improved lower bound found for multicommodity flow on trees
Improved Integrality Gap for Multicommodity Flow on Trees
Data Structures and Algorithms
Summary
The paper deals with a math problem about how well you can route multiple requests through a tree-like network. The authors improve the best known limit that shows how close a simple mathematical solution can get to the best actual solution. They first find an intermediate step using a simple idea, then refine it to get an even better result. This helps better understand the difficulty of dividing flow in these kinds of networks.
What this means in practice
- •For network schedulers: Improve understanding of routing limitations in tree-structured networks to guide scheduling and resource allocation.
- •For logistics planners: Better characterize flow constraints in hierarchical distribution networks, helping to plan delivery routes and loads more realistically.
A theory result. No direct application yet.
Authors
Elfarouk Harb
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$.