On linear programming relaxations for unsplittable flow in trees

DOI10.4230/LIPICS.APPROX-RANDOM.2015.265MaRDI QIDQ5351906zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs
• Approximation algorithms for the unsplittable flow problem on paths and trees
• Constant integrality gap LP formulations of unsplittable flow on a path
• Submodular unsplittable flow on trees
• Submodular unsplittable flow on trees

Cited in

(8)

• Submodular unsplittable flow on trees
• Submodular unsplittable flow on trees
• Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs
• scientific article; zbMATH DE number 6861995 (Why is no real title available?)
• scientific article; zbMATH DE number 828003 (Why is no real title available?)
• Constant integrality gap LP formulations of unsplittable flow on a path
• A constant factor approximation algorithm for the storage allocation problem
• A knapsack intersection hierarchy

This page was built for publication: On linear programming relaxations for unsplittable flow in trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5351906)