New Approximation Schemes for Unsplittable Flow on a Path

DOI10.1137/1.9781611973730.5zbMath1372.68296OpenAlexW4235331094MaRDI QIDQ5363081

Amit Kumar, Tobias Mömke, Andreas Wiese, Naveen Garg, Jatin Batra

Publication date: 5 October 2017

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

Full work available at URL: https://doi.org/10.1137/1.9781611973730.5

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Flows in graphs (05C21)

Related Items (13)

A $$(2+\epsilon )$$-Approximation Algorithm for the Storage Allocation Problem ⋮ Submodular Unsplittable Flow on Trees ⋮ General caching is hard: even with small pages ⋮ Approximations for generalized unsplittable flow on paths with application to power systems optimization ⋮ Temporal flows in temporal networks ⋮ Approximation algorithms for the generalized incremental knapsack problem ⋮ Improved Algorithm for Resource Allocation Problems ⋮ Fixed-parameter algorithms for unsplittable flow cover ⋮ A constant factor approximation algorithm for the storage allocation problem ⋮ Flexible resource allocation to interval jobs ⋮ Unnamed Item ⋮ Pricing on Paths: A PTAS for the Highway Problem ⋮ Submodular unsplittable flow on trees

This page was built for publication: New Approximation Schemes for Unsplittable Flow on a Path