A mazing 2+ approximation for unsplittable flow on a path

DOI10.1145/3242769MaRDI QIDQ4629969zbMATH OpenOpenAlexWikidataFDO

Authors Aris Anagnostopoulos, Fabrizio Grandoni, Andreas Wiese, Stefano Leonardi

Publication date 28 March 2019

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3242769

zbMATH Keywords

approximation algorithms

Mathematics Subject Classification ID

Flows in graphs (05C21) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• A Mazing 2+∊ Approximation for Unsplittable Flow on a Path
• A (5/3+)-approximation for unsplittable flow on a path: placing small tasks into boxes
• A (1+)-approximation for unsplittable flow on a path in fixed-parameter running time
• New approximation schemes for unsplittable flow on a path
• A constant-factor approximation algorithm for unsplittable flow on paths

Cited in

(17)

• Approximations for generalized unsplittable flow on paths with application to power systems optimization
• Improved algorithms for scheduling unsplittable flows on paths
• Approximation algorithms for the generalized incremental knapsack problem
• Improved approximation algorithms for unsplittable flow on a path with time windows
• scientific article; zbMATH DE number 5899246 (Why is no real title available?)
• A (2+)-approximation algorithm for the storage allocation problem
• To augment or not to augment: solving unsplittable flow on a path by creating slack
• scientific article; zbMATH DE number 7051239 (Why is no real title available?)
• A (1+)-approximation for unsplittable flow on a path in fixed-parameter running time
• 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
• New approximation schemes for unsplittable flow on a path
• A Mazing 2+∊ Approximation for Unsplittable Flow on a Path
• A constant-factor approximation algorithm for unsplittable flow on paths
• A constant factor approximation algorithm for unsplittable flow on paths
• A logarithmic approximation for unsplittable flow on line graphs
• The parameterized complexity landscape of the unsplittable flow problem

This page was built for publication: A mazing \(2+\epsilon\) approximation 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 Q4629969)