A constant factor approximation algorithm for unsplittable flow on paths

DOI10.1109/FOCS.2011.10MaRDI QIDQ5494961zbMATH OpenOpenAlexFDO

Authors Paul Bonsma, Jens Schulz, Andreas Wiese

Publication date 30 July 2014

Published in 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/focs.2011.10

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Approximation algorithms (68W25)

Recommendations

• A constant-factor approximation algorithm for unsplittable flow on paths
• A Mazing 2+∊ Approximation for Unsplittable Flow on a Path
• A (1+)-approximation for unsplittable flow on a path in fixed-parameter running time
• Approximation algorithms for the unsplittable flow problem on paths and trees
• A mazing \(2+\epsilon\) approximation for unsplittable flow on a path

Cited in

(36)

• Approximation Algorithms for Edge-Disjoint Paths and Unsplittable Flow
• Scheduling split intervals with non-uniform demands
• Approximation algorithms for round-UFP and round-SAP
• A note on the greedy algorithm for the unsplittable flow problem
• A (5/3+)-approximation for unsplittable flow on a path: placing small tasks into boxes
• The parameterized complexity landscape of the unsplittable flow problem
• Stochastic unsplittable flows
• Improved algorithms for resource allocation under varying capacity
• Independent set of convex polygons: from \(n^{\epsilon}\) to \(1+\epsilon \) via shrinking
• Scheduling Resources for Throughput Maximization
• Resource allocation problem under single resource assignment
• Constant integrality gap LP formulations of unsplittable flow on a path
• How unsplittable-flow-covering helps scheduling with job-dependent cost functions
• A constant-factor approximation algorithm for unsplittable flow on paths
• Packing cars into narrow roads: PTASs for limited supply highway
• scientific article; zbMATH DE number 7051239 (Why is no real title available?)
• Partial convexification of general mips by Dantzig-Wolfe reformulation
• Pricing on paths: a PTAS for the highway problem
• scientific article; zbMATH DE number 7278054 (Why is no real title available?)
• scientific article; zbMATH DE number 5899246 (Why is no real title available?)
• A near-linear time constant factor algorithm for unsplittable flow problem on line with bag constraints
• Approximation algorithms for the ring loading problem with penalty cost
• Infinite product exponents for modular forms
• Optimal interval scheduling with a resource constraint
• Approximation algorithms for the unsplittable flow problem on paths and trees
• A logarithmic approximation for unsplittable flow on line graphs
• Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs
• Approximation algorithms for the unsplittable flow problem
• A (1+)-approximation for unsplittable flow on a path in fixed-parameter running time
• Improved algorithms for scheduling unsplittable flows on paths
• Approximations for generalized unsplittable flow on paths with application to power systems optimization
• Improved algorithm for resource allocation problems
• Coloring and maximum independent set of rectangles
• A constant factor approximation algorithm for the storage allocation problem
• Multicommodity flow in trees: packing via covering and iterated relaxation
• A Mazing 2+∊ Approximation for Unsplittable Flow on a Path

This page was built for publication: A constant factor approximation algorithm for unsplittable flow on paths

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