Max-Weight Integral Multicommodity Flow in Spiders and High-Capacity Trees

摘要: We consider the max-weight integral multicommodity flow problem in trees. In this we are given an edge-capacitated tree and weighted pairs of terminals, objective is to find a between terminal subject capacities. This was shown be $\mathcal{\mathsf{APX}}$-hard by Garg, Vazirani Yannakakis [Algorithmica, 1997], 4-approximation Chekuri, Mydlarz Shepherd [ACM Trans. Alg., 2007]. Some special cases known exactly solvable polynomial time, including when graph path or star. First, every edge has capacity at least μ ≥ 2, use iterated LP relaxation obtain improved approximation ratio min {3, 1 + 4/μ + 6/(μ 2 − μ)}. show bounds integrality gap natural relaxation. A complementary hardness result yields 1 + Θ(1/μ) threshold approximability (if P ≠ NP). Second, extend range instances for which exact solutions can found efficiently. When spider (i.e. if only one vertex degree greater than 2) give polynomial-time algorithm optimal solution, as well polyhedral description convex hull all feasible solutions.