Improved Integrality Gap for Multicommodity Flow on Trees

Elfarouk Harb

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 Chek…