Approximation algorithms for the unsplittable flow problem on paths and trees

DOI10.4230/LIPICS.FSTTCS.2012.267zbMATH Open1354.68297OpenAlexW756921666MaRDI QIDQ2957504FDOQ2957504

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

Publication date: 26 January 2017

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

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

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)

Cited In (19)

• Complex-demand scheduling problem with application in smart grid
• Temporal flows in temporal networks
• Scheduling split intervals with non-uniform demands
• Improved algorithms for resource allocation under varying capacity
• Title not available (Why is that?)
• Title not available (Why is that?)
• Flows on few paths: Algorithms and lower bounds
• Title not available (Why is that?)
• Title not available (Why is that?)
• The prize-collecting call control problem on weighted lines and rings
• Combinatorial algorithms for the unsplittable flow problem
• 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
• Title not available (Why is that?)
• Approximation algorithms for the unsplittable flow problem
• Improved algorithms for scheduling unsplittable flows on paths
• Approximations for generalized unsplittable flow on paths with application to power systems optimization
• Approximation Algorithms for Edge-Disjoint Paths and Unsplittable Flow

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)