Approximation algorithms for the unsplittable flow problem

DOI10.1007/3-540-45753-4_7MaRDI QIDQ4411277zbMATH OpenFDO

Authors Amit Chakrabarti, Chandra Chekuri, Anupam Gupta, Amit Kumar

Publication date 7 July 2003

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2462/24620051.htm, https://figshare.com/articles/journal_contribution/Approximation_Algorithms_for_the_Unsplittable_Flow_Problem/6603611

Mathematics Subject Classification ID

Approximation algorithms (68W25) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Approximation algorithms for the unsplittable flow problem
• Combinatorial algorithms for the unsplittable flow problem
• Approximation algorithms for single-source unsplittable flow
• Strongly polynomial algorithms for the unsplittable flow problem
• On the single-source unsplittable flow problem

Cited in

(30)

• Resource allocation in bounded degree trees
• A note on the greedy algorithm for the unsplittable flow problem
• A fixed-parameter tractability result for multicommodity demand flow in trees
• On the single-source unsplittable flow problem
• How unsplittable-flow-covering helps scheduling with job-dependent cost functions
• NP-hardness of broadcast scheduling and inapproximability of single-source unsplittable min-cost flow
• Combinatorial algorithms for the unsplittable flow problem
• Meet and merge: approximation algorithms for confluent flows
• Improved algorithms for scheduling unsplittable flows on paths
• Combinatorial approximation algorithms for generalized flow problems
• Approximation algorithms for single-source unsplittable flow
• A near-linear time constant factor algorithm for unsplittable flow problem on line with bag constraints
• Truthful unsplittable flow for large capacity networks
• A quasi-PTAS for unsplittable flow on line graphs
• Approximation algorithms for the unsplittable flow problem on paths and trees
• Improved bounds for the unsplittable flow problem
• Implementing approximation algorithms for the single-source unsplittable flow problem
• New Algorithms for the Unsplittable Flow Problem
• Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs
• Strongly polynomial algorithms for the unsplittable flow problem
• scientific article; zbMATH DE number 1775441 (Why is no real title available?)
• The inapproximability of maximum single-sink unsplittable, priority and confluent flow problems
• scientific article; zbMATH DE number 7051239 (Why is no real title available?)
• Stochastic unsplittable flows
• scientific article; zbMATH DE number 7278054 (Why is no real title available?)
• Approximation Algorithms for Edge-Disjoint Paths and Unsplittable Flow
• A logarithmic approximation for unsplittable flow on line graphs
• A knapsack intersection hierarchy
• The \(k\)-splittable flow problem
• Approximation algorithms for the unsplittable flow problem

This page was built for publication: Approximation algorithms for the unsplittable flow problem

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