A Constant-Factor Approximation Algorithm for Unsplittable Flow on Paths
From MaRDI portal
Publication:5494938
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
resource allocationstrong NP-hardnessmaximum weight independent setunsplittable flowconstant-factor approximation
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
