{"id":"arxiv/2609.07949","url":"https://arxiv.org/abs/2609.07949","tags":["cs.DS","math.CO"],"score":0,"title":"Improved Integrality Gap for Multicommodity Flow on Trees","domain":"cs.DS","source":"arxiv","authors":["Elfarouk Harb"],"reviews":0,"subject":"cs.DS","summary":"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$.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-07","reactions":{}}