Summary
This paper looks at a problem in managing how different demands share a network that looks like a tree. The authors improved previous math that shows how close a simple solution is to the best possible one. They first found an intermediate result using a new simple method, then refined it to get an even better estimate. Their work helps us understand limits in designing efficient communication or transportation in tree-like networks.
integrality gapmulticommodity flowunit-demandtreespacking lemmainductive coloringnetwork flowapproximationlower bound
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$.