A logarithmic approximation for unsplittable flow on line graphs

DOI10.1145/2532645zbMath1321.68493OpenAlexW2126874118MaRDI QIDQ5501955

Zachary Friggstad, Nikhil Bansal, Mohammad R. Salavatipour, Rohit Khandekar

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

schedulingapproximation algorithmsunsplittable flowresource allocation problem

Mathematics Subject Classification ID

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

Related Items (11)

Improved algorithms for resource allocation under varying capacity ⋮ Optimal interval scheduling with a resource constraint ⋮ Approximations for generalized unsplittable flow on paths with application to power systems optimization ⋮ How unsplittable-flow-covering helps scheduling with job-dependent cost functions ⋮ A constant factor approximation algorithm for the storage allocation problem ⋮ Caching is hard -- even in the fault model ⋮ On the complexity of interval scheduling with a resource constraint ⋮ Pricing on Paths: A PTAS for the Highway Problem ⋮ The Prize-collecting Call Control Problem on Weighted Lines and Rings ⋮ Unnamed Item ⋮ A logarithmic approximation for unsplittable flow on line graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Primal-dual approximation algorithms for integral flow and multicut in trees
• The directed subgraph homeomorphism problem
• Approximation Algorithms for Disjoint Paths and Related Routing and Packing Problems
• A quasi-PTAS for unsplittable flow on line graphs
• An improved approximation algorithm for resource allocation
• 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
• Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• A Constant Factor Approximation Algorithm for Unsplittable Flow on Paths
• A logarithmic approximation for unsplittable flow on line graphs
• A unified approach to approximating resource allocation and scheduling
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems

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