A logarithmic approximation for unsplittable flow on line graphs

DOI10.1145/2532645zbMATH Open1321.68493OpenAlexW2126874118MaRDI QIDQ5501955FDOQ5501955

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

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

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)

Cites Work

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

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
• Title not available (Why is that?)
• Pricing on paths: a PTAS for the highway problem
• Title not available (Why is that?)
• The prize-collecting call control problem on weighted lines and rings
• Optimal interval scheduling with a resource constraint
• A logarithmic approximation for unsplittable flow on line graphs
• On the complexity of interval scheduling with a resource constraint
• 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)