A constant-factor approximation algorithm for unsplittable flow on paths

DOI10.1137/120868360MaRDI QIDQ5494938zbMATH OpenOpenAlexFDO

Authors Paul Bonsma, Jens Schulz, Andreas Wiese

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

constant-factor approximationmaximum weight independent setresource allocationstrong NP-hardnessunsplittable flow

Mathematics Subject Classification ID

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

Recommendations

• A constant factor approximation algorithm for unsplittable flow on paths
• A Mazing 2+∊ Approximation for Unsplittable Flow on a Path
• A mazing \(2+\epsilon\) approximation for unsplittable flow on a path
• A (1+)-approximation for unsplittable flow on a path in fixed-parameter running time
• New approximation schemes for unsplittable flow on a path

Cited in

(34)

• Submodular unsplittable flow on trees
• An iterative dynamic programming approach for the temporal knapsack problem
• Infinite product exponents for modular forms
• Improved algorithms for scheduling unsplittable flows on paths
• Approximation algorithms for the generalized incremental knapsack problem
• Fixed-parameter algorithms for unsplittable flow cover
• The prize-collecting call control problem on weighted lines and rings
• A near-linear time constant factor algorithm for unsplittable flow problem on line with bag constraints
• scientific article; zbMATH DE number 5899246 (Why is no real title available?)
• Submodular unsplittable flow on trees
• A (2+)-approximation algorithm for the storage allocation problem
• Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs
• A mazing \(2+\epsilon\) approximation for unsplittable flow on a path
• scientific article; zbMATH DE number 7051239 (Why is no real title available?)
• Constant integrality gap LP formulations of unsplittable flow on a path
• scientific article; zbMATH DE number 7278054 (Why is no real title available?)
• A constant factor approximation algorithm for the storage allocation problem
• New approximation schemes for unsplittable flow on a path
• A Mazing 2+∊ Approximation for Unsplittable Flow on a Path
• Approximation Algorithms for Edge-Disjoint Paths and Unsplittable Flow
• A constant factor approximation algorithm for unsplittable flow on paths
• A logarithmic approximation for unsplittable flow on line graphs
• Solving the temporal knapsack problem via recursive Dantzig-Wolfe reformulation
• A knapsack intersection hierarchy
• On improved interval cover mechanisms for crowdsourcing markets
• Integer optimization models and algorithms for the multi-period non-shareable resource allocation problem
• Breaking the barrier of 2 for the storage allocation problem
• On the approximability of unsplittable flow on a path with time windows
• Approximating the maximum independent set of convex polygons with a bounded number of directions
• The B-prize-collecting multicut problem in paths, spider graphs and rings
• The parameterized complexity landscape of the unsplittable flow problem
• Parameterized approximation for maximum weight independent set of rectangles and segments
• Unsplittable flow on a short path
• Approximation algorithms for the unsplittable flow problem

This page was built for publication: A constant-factor approximation algorithm for unsplittable flow on paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5494938)