On Linear Programming Relaxations for Unsplittable Flow in Trees

DOI10.4230/LIPIcs.APPROX-RANDOM.2015.265zbMath1375.68217OpenAlexW2276905128MaRDI QIDQ5351906

Zachary Friggstad, Zhihan Gao

Publication date: 31 August 2017

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2015/5307/pdf/17.pdf/

zbMATH Keywords

approximation algorithmlinear programming relaxationunsplittable flow

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (4)

Submodular Unsplittable Flow on Trees ⋮ A knapsack intersection hierarchy ⋮ A constant factor approximation algorithm for the storage allocation problem ⋮ Submodular unsplittable flow on trees

This page was built for publication: On Linear Programming Relaxations for Unsplittable Flow in Trees