A Constant Factor Approximation Algorithm for Unsplittable Flow on Paths
From MaRDI portal
Publication:5494961
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
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