A logarithmic approximation for unsplittable flow on line graphs

DOI10.1145/2532645MaRDI QIDQ5501955zbMATH OpenOpenAlexFDO

Authors N. Bansal, Zachary Friggstad, Rohit Khandekar, Mohammad Salavatipour

Publication date 14 August 2015

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

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

zbMATH Keywords

approximation algorithmsschedulingunsplittable flowresource allocation problem

Mathematics Subject Classification ID

Linear programming (90C05) Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39) Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Approximation algorithms (68W25)

Recommendations

• scientific article; zbMATH DE number 7051239
• A quasi-PTAS for unsplittable flow on line graphs
• Approximation algorithms for the unsplittable flow problem
• scientific article; zbMATH DE number 1947047
• Approximation algorithms for the unsplittable flow problem on paths and trees
• New approximation schemes 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 \((1+\varepsilon)\)-approximation for unsplittable flow on a path in fixed-parameter running time
• A mazing \(2+\epsilon\) approximation for unsplittable flow on a path

Cites work

• scientific article; zbMATH DE number 5899246 (Why is no real title available?)
• scientific article; zbMATH DE number 1947047 (Why is no real title available?)
• scientific article; zbMATH DE number 1757944 (Why is no real title available?)
• scientific article; zbMATH DE number 1445370 (Why is no real title available?)
• scientific article; zbMATH DE number 1445390 (Why is no real title available?)
• A constant factor approximation algorithm for unsplittable flow on paths
• A logarithmic approximation for unsplittable flow on line graphs
• A quasi-PTAS for unsplittable flow on line graphs
• A unified approach to approximating resource allocation and scheduling
• An improved approximation algorithm for \textsc{Resource Allocation}
• Approximation algorithms for disjoint paths and related routing and packing problems
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Improved bounds for the unsplittable flow problem
• Logarithmic hardness of the undirected edge-disjoint paths problem
• Multicommodity demand flow in a tree and packing integer programs
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
• Primal-dual approximation algorithms for integral flow and multicut in trees
• The directed subgraph homeomorphism problem
• Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs

Cited in

(13)

• Caching is hard -- even in the fault model
• Improved algorithms for resource allocation under varying capacity
• How unsplittable-flow-covering helps scheduling with job-dependent cost functions
• scientific article; zbMATH DE number 7051239 (Why is no real title available?)
• Pricing on paths: a PTAS for the highway problem
• scientific article; zbMATH DE number 7278054 (Why is no real title available?)
• The prize-collecting call control problem on weighted lines and rings
• Optimal interval scheduling with a resource constraint
• On the complexity of interval scheduling with a resource constraint
• A logarithmic approximation for unsplittable flow on line graphs
• Approximations for generalized unsplittable flow on paths with application to power systems optimization
• The preemptive resource allocation problem
• A constant factor approximation algorithm for the storage allocation problem

This page was built for publication: A logarithmic approximation for unsplittable flow on line graphs

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