New approximation schemes for unsplittable flow on a path

DOI10.1137/1.9781611973730.5MaRDI QIDQ5363081zbMATH OpenOpenAlexFDO

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

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

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

Recommendations

• 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
• To augment or not to augment: solving unsplittable flow on a path by creating slack
• A constant-factor approximation algorithm for unsplittable flow on paths

Cited in

(29)

• Submodular unsplittable flow on trees
• Flexible resource allocation to interval jobs
• Approximations for generalized unsplittable flow on paths with application to power systems optimization
• Approximation algorithms for the generalized incremental knapsack problem
• Fixed-parameter algorithms for unsplittable flow cover
• Pricing on paths: a PTAS for the highway problem
• 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
• To augment or not to augment: solving unsplittable flow on a path by creating slack
• Improved algorithm for resource allocation problems
• A mazing \(2+\epsilon\) approximation for unsplittable flow on a path
• scientific article; zbMATH DE number 7051239 (Why is no real title available?)
• Packing cars into narrow roads: PTASs for limited supply highway
• A (1+)-approximation for unsplittable flow on a path in fixed-parameter running time
• scientific article; zbMATH DE number 7278054 (Why is no real title available?)
• A (5/3+)-approximation for unsplittable flow on a path: placing small tasks into boxes
• A constant factor approximation algorithm for the storage allocation problem
• A Mazing 2+∊ Approximation for Unsplittable Flow on a Path
• A constant-factor approximation algorithm for unsplittable flow on paths
• A logarithmic approximation for unsplittable flow on line graphs
• 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
• Approximation algorithms for round-UFP and round-SAP
• Improved polynomial-time approximations for clustering with minimum sum of radii or diameters
• The parameterized complexity landscape of the unsplittable flow problem
• Approximation algorithms for clustering with minimum sum of radii, diameters, and squared radii
• Unsplittable flow on a short path

This page was built for publication: New approximation schemes for unsplittable flow on a path

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