A Constant Factor Approximation Algorithm for Unsplittable Flow on Paths

DOI10.1109/FOCS.2011.10zbMath1292.68162OpenAlexW2127719709MaRDI QIDQ5494961

Andreas Wiese, Paul Bonsma, Jens Schulz

Publication date: 30 July 2014

Published in: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/focs.2011.10

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

Improved algorithms for resource allocation under varying capacity, Resource allocation problem under single resource assignment, Optimal interval scheduling with a resource constraint, Improved algorithms for scheduling unsplittable flows on paths, Improved Algorithm for Resource Allocation Problems, Scheduling split intervals with non-uniform demands, Stochastic Unsplittable Flows, Independent set of convex polygons: from \(n^{\epsilon}\) to \(1+\epsilon \) via shrinking, Partial Convexification of General MIPs by Dantzig-Wolfe Reformulation, How unsplittable-flow-covering helps scheduling with job-dependent cost functions, Multicommodity flow in trees: packing via covering and iterated relaxation, Unnamed Item, Pricing on Paths: A PTAS for the Highway Problem, Scheduling Resources for Throughput Maximization, Coloring and Maximum Independent Set of Rectangles, Unnamed Item, A logarithmic approximation for unsplittable flow on line graphs, Approximation algorithms for the ring loading problem with penalty cost