A Mazing 2+∊ Approximation for Unsplittable Flow on a Path
From MaRDI portal
Publication:5383962
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
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