A Constant-Factor Approximation Algorithm for Unsplittable Flow on Paths

DOI10.1137/120868360zbMath1297.68185OpenAlexW2175156623MaRDI QIDQ5494938

Andreas Wiese, Paul Bonsma, Jens Schulz

Publication date: 30 July 2014

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

resource allocationstrong NP-hardnessmaximum weight independent setunsplittable flowconstant-factor approximation

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (12)

A $$(2+\epsilon )$$-Approximation Algorithm for the Storage Allocation Problem ⋮ Submodular Unsplittable Flow on Trees ⋮ General caching is hard: even with small pages ⋮ Approximation algorithms for the generalized incremental knapsack problem ⋮ A knapsack intersection hierarchy ⋮ On improved interval cover mechanisms for crowdsourcing markets ⋮ Fixed-parameter algorithms for unsplittable flow cover ⋮ A constant factor approximation algorithm for the storage allocation problem ⋮ An iterative dynamic programming approach for the temporal knapsack problem ⋮ The Prize-collecting Call Control Problem on Weighted Lines and Rings ⋮ Solving the temporal knapsack problem via recursive Dantzig-Wolfe reformulation ⋮ Submodular unsplittable flow on trees

This page was built for publication: A Constant-Factor Approximation Algorithm for Unsplittable Flow on Paths