Constant Integrality Gap LP Formulations of Unsplittable Flow on a Path

DOI10.1007/978-3-642-36694-9_3zbMath1331.90086OpenAlexW1604629374WikidataQ116754398 ScholiaQ116754398MaRDI QIDQ4910802

Fabrizio Grandoni, Andreas Wiese, Aris Anagnostopoulos, Stefano Leonardi

Publication date: 19 March 2013

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-36694-9_3

zbMATH Keywords

Unsplittable Flow Problem on a Path (UFPP)

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items (7)

Improved algorithms for resource allocation under varying capacity ⋮ Complex-demand scheduling problem with application in smart grid ⋮ Independent set of convex polygons: from \(n^{\epsilon}\) to \(1+\epsilon \) via shrinking ⋮ A constant factor approximation algorithm for the storage allocation problem ⋮ Unnamed Item ⋮ Pricing on Paths: A PTAS for the Highway Problem ⋮ Unnamed Item

This page was built for publication: Constant Integrality Gap LP Formulations of Unsplittable Flow on a Path