A Mazing 2+∊ Approximation for Unsplittable Flow on a Path

DOI10.1137/1.9781611973402.3zbMath1422.68279arXiv1211.2670OpenAlexW3209212021MaRDI QIDQ5383962

Aris Anagnostopoulos, Andreas Wiese, Fabrizio Grandoni, Stefano Leonardi

Publication date: 20 June 2019

Published in: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1211.2670

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25) Flows in graphs (05C21)

Related Items

Improved algorithms for resource allocation under varying capacity, A $$(2+\epsilon )$$-Approximation Algorithm for the Storage Allocation Problem, Resource allocation problem under single resource assignment, General caching is hard: even with small pages, Approximations for generalized unsplittable flow on paths with application to power systems optimization, Improved Algorithm for Resource Allocation Problems, Scheduling split intervals with non-uniform demands, Complex-demand scheduling problem with application in smart grid, Stochastic Unsplittable Flows, How unsplittable-flow-covering helps scheduling with job-dependent cost functions, A constant factor approximation algorithm for the storage allocation problem, Unnamed Item, Pricing on Paths: A PTAS for the Highway Problem, Submodular unsplittable flow on trees