A (5/3 + ε)-approximation for unsplittable flow on a path: placing small tasks into boxes

DOI10.1145/3188745.3188894zbMath1422.68298OpenAlexW2809199312MaRDI QIDQ5230324

Fabrizio Grandoni, Hang Zhou, Tobias Mömke, Andreas Wiese

Publication date: 22 August 2019

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

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

zbMATH Keywords

approximation algorithmsunsplittable flow on path

Mathematics Subject Classification ID

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

Related Items (7)

Peak demand minimization via sliced strip packing ⋮ 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 ⋮ Flexible resource allocation to interval jobs ⋮ Unnamed Item ⋮ Closing the Gap for Pseudo-Polynomial Strip Packing

This page was built for publication: A (5/3 + ε)-approximation for unsplittable flow on a path: placing small tasks into boxes