Approximation algorithms for the unsplittable flow problem on paths and trees

DOI10.4230/LIPICS.FSTTCS.2012.267MaRDI QIDQ2957504zbMATH OpenOpenAlexFDO

Authors Naveen Garg, Divya Gupta, Amit Kumar, Vishal Narula, Arindam Pal, Khaled Elbassioni

Publication date 26 January 2017

Full work available at URL https://doi.org/10.4230/LIPIcs.FSTTCS.2012.267

zbMATH Keywords

linear programmingapproximation algorithmsschedulinginteger decompositionunsplittable flows

Mathematics Subject Classification ID

Linear programming (90C05) Deterministic network models in operations research (90B10) Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25)

Recommendations

• Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs
• scientific article; zbMATH DE number 1947047
• scientific article; zbMATH DE number 1757944
• Approximation algorithms for the unsplittable flow problem
• A constant factor approximation algorithm for unsplittable flow on paths

Cited in

(24)

• Approximation Algorithms for Edge-Disjoint Paths and Unsplittable Flow
• Scheduling split intervals with non-uniform demands
• Approximation algorithms for round-UFP and round-SAP
• Improved bounds for the unsplittable flow problem
• Improved algorithms for resource allocation under varying capacity
• Improved approximation algorithms for unsplittable flow on a path with time windows
• Constant integrality gap LP formulations of unsplittable flow on a path
• On linear programming relaxations for unsplittable flow in trees
• scientific article; zbMATH DE number 828003 (Why is no real title available?)
• scientific article; zbMATH DE number 7051239 (Why is no real title available?)
• Flows on few paths: Algorithms and lower bounds
• scientific article; zbMATH DE number 7278054 (Why is no real title available?)
• scientific article; zbMATH DE number 5899246 (Why is no real title available?)
• The prize-collecting call control problem on weighted lines and rings
• Combinatorial algorithms for the unsplittable flow problem
• Submodular unsplittable flow on trees
• A logarithmic approximation for unsplittable flow on line graphs
• Submodular unsplittable flow on trees
• Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs
• Approximation algorithms for the unsplittable flow problem
• scientific article; zbMATH DE number 1757944 (Why is no real title available?)
• Improved algorithms for scheduling unsplittable flows on paths
• Approximations for generalized unsplittable flow on paths with application to power systems optimization
• A constant factor approximation algorithm for unsplittable flow on paths

This page was built for publication: Approximation algorithms for the unsplittable flow problem on paths and trees

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