Approximation algorithms for the unsplittable flow problem

DOI10.1007/s00453-006-1210-5zbMath1107.68120MaRDI QIDQ868438

Amit Chakrabarti, Amit Kumar, Chandra Chekuri, Anupam Gupta

Publication date: 5 March 2007

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://figshare.com/articles/journal_contribution/Approximation_Algorithms_for_the_Unsplittable_Flow_Problem/6603611

Mathematics Subject Classification ID

68W25: Approximation algorithms

Related Items

Unnamed Item, Stochastic Makespan Minimization in Structured Set Systems (Extended Abstract), Unnamed Item, Stochastic Unsplittable Flows, Algebraic Theory on Shortest Paths for All Flows, Optimal interval scheduling with a resource constraint, A constant factor approximation algorithm for the storage allocation problem, Maximum bipartite flow in networks with adaptive channel width, Resource allocation with time intervals, Improved algorithms for resource allocation under varying capacity, Complex-demand scheduling problem with application in smart grid, Submodular unsplittable flow on trees, Stochastic makespan minimization in structured set systems, Scheduling split intervals with non-uniform demands, Algebraic theory on shortest paths for all flows, Approximations for generalized unsplittable flow on paths with application to power systems optimization, Pricing on Paths: A PTAS for the Highway Problem, The Prize-collecting Call Control Problem on Weighted Lines and Rings, Scheduling Resources for Throughput Maximization, Submodular Unsplittable Flow on Trees, A $$(2+\epsilon )$$-Approximation Algorithm for the Storage Allocation Problem