A quasi-PTAS for unsplittable flow on line graphs

DOI10.1145/1132516.1132617zbMath1301.68264OpenAlexW2069417991MaRDI QIDQ2931432

Nikhil Bansal, Amir Epstein, Baruch Schieber, Amit Chakrabarti

Publication date: 25 November 2014

Published in: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

schedulingresource allocationapproximation algorithmsapproximation schemeunsplittable flow

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Flows in graphs (05C21)

Related Items (35)

Mallows-Smoothed Distribution over Rankings Approach for Modeling Choice ⋮ Improved algorithms for resource allocation under varying capacity ⋮ Flexible bandwidth assignment with application to optical networks ⋮ A $$(2+\epsilon )$$-Approximation Algorithm for the Storage Allocation Problem ⋮ Submodular Unsplittable Flow on Trees ⋮ Resource allocation problem under single resource assignment ⋮ General caching is hard: even with small pages ⋮ Resource allocation with time intervals ⋮ Approximations for generalized unsplittable flow on paths with application to power systems optimization ⋮ Improved algorithms for scheduling unsplittable flows on paths ⋮ Capacitated max-batching with interval graph compatibilities ⋮ Approximation algorithms for the generalized incremental knapsack problem ⋮ A knapsack intersection hierarchy ⋮ On improved interval cover mechanisms for crowdsourcing markets ⋮ Improved Algorithm for Resource Allocation Problems ⋮ Fixed-parameter algorithms for unsplittable flow cover ⋮ Scheduling split intervals with non-uniform demands ⋮ Complex-demand scheduling problem with application in smart grid ⋮ An LP-rounding \(2\sqrt{2}\)-approximation for restricted maximum acyclic subgraph ⋮ How unsplittable-flow-covering helps scheduling with job-dependent cost functions ⋮ A constant factor approximation algorithm for the storage allocation problem ⋮ Flexible resource allocation to interval jobs ⋮ Improving LTL truck load utilization on line ⋮ Caching is hard -- even in the fault model ⋮ Unnamed Item ⋮ Clique clustering yields a PTAS for max-coloring interval graphs ⋮ Pricing on Paths: A PTAS for the Highway Problem ⋮ The Prize-collecting Call Control Problem on Weighted Lines and Rings ⋮ Near-Optimal Algorithms for the Assortment Planning Problem Under Dynamic Substitution and Stochastic Demand ⋮ Submodular unsplittable flow on trees ⋮ Scheduling Resources for Throughput Maximization ⋮ Resource allocation in bounded degree trees ⋮ Unnamed Item ⋮ A logarithmic approximation for unsplittable flow on line graphs ⋮ Approximation algorithms for the ring loading problem with penalty cost

This page was built for publication: A quasi-PTAS for unsplittable flow on line graphs