Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs

DOI10.1007/978-3-642-03685-9_4MaRDI QIDQ3638868zbMATH OpenOpenAlexFDO

Authors Chandra Chekuri, Alina Ene, Nitish Korula

Publication date 28 October 2009

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-03685-9_4

Mathematics Subject Classification ID

Approximation algorithms (68W25) Integer programming (90C10) Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• On linear programming relaxations for unsplittable flow in trees
• Approximation algorithms for the unsplittable flow problem on paths and trees
• Combinatorial algorithms for the unsplittable flow problem
• scientific article; zbMATH DE number 1775441
• Approximation algorithms for the unsplittable flow problem
• scientific article; zbMATH DE number 1947047
• Improved bounds for the unsplittable flow problem
• A constant-factor approximation algorithm for unsplittable flow on paths
• A constant factor approximation algorithm for unsplittable flow on paths
• FPT and FPT-Approximation Algorithms for Unsplittable Flow on Trees

Cited in

(22)

• Improved algorithms for resource allocation under varying capacity
• Submodular unsplittable flow on trees
• On some efficiently solvable classes of the network facility location problem with constraints on the capacities of communication lines
• Parametric power supply networks
• Pricing on paths: a PTAS for the highway problem
• The prize-collecting call control problem on weighted lines and rings
• Approximation algorithms for the unsplittable flow problem on paths and trees
• Iterative packing for demand and hypergraph matching
• Submodular unsplittable flow on trees
• A (2+)-approximation algorithm for the storage allocation problem
• Constant integrality gap LP formulations of unsplittable flow on a path
• Parametric power supply networks (extended abstract)
• Stochastic unsplittable flows
• Packing cars into narrow roads: PTASs for limited supply highway
• A constant factor approximation algorithm for the storage allocation problem
• On linear programming relaxations for unsplittable flow in trees
• A logarithmic approximation for unsplittable flow on line graphs
• A knapsack intersection hierarchy
• Approximability of sparse integer programs
• Breaking the barrier of 2 for the storage allocation problem
• The parameterized complexity landscape of the unsplittable flow problem
• Unsplittable flow on a short path

This page was built for publication: Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs

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