A PTAS for unsplittable flow on a path

DOI10.1145/3519935.3519959MaRDI QIDQ6083485zbMATH OpenOpenAlexFDO

Authors Fabrizio Grandoni, Tobias Mömke, Andreas Wiese

Publication date 8 December 2023

Published in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

approximationdynamic programmingunsplittable flow

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cited in

(9)

• A Mazing 2+∊ Approximation for Unsplittable Flow on a Path
• 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
• 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
• Improved approximation guarantees for advertisement placement

This page was built for publication: A PTAS 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 Q6083485)