Approximation Algorithms for Disjoint Paths and Related Routing and Packing Problems
From MaRDI portal
Publication:2757635
DOI10.1287/moor.25.2.255.12228zbMath0977.90069MaRDI QIDQ2757635
Aravind Srinivasan, Alok Baveja
Publication date: 26 November 2001
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/moor.25.2.255.12228
linear programming; integer programming; packing; approximation algorithms; randomized algorithms; routing; multicommodity flow; rounding; disjoint paths; unsplittable flow
90C35: Programming involving graphs or networks
68Q25: Analysis of algorithms and problem complexity
Related Items
A logarithmic approximation for unsplittable flow on line graphs, Flows with Unit Path Capacities and Related Packing and Covering Problems, Solving the edge‐disjoint paths problem using a two‐stage method, LS(graph): a constraint-based local search for constraint optimization on trees and paths, Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs, Minimal multicut and maximal integer multiflow: a survey, Disjoint paths in sparse graphs, A note on the greedy algorithm for the unsplittable flow problem, Flows with unit path capacities and related packing and covering problems, Approximating covering integer programs with multiplicity constraints, Approximating low-congestion routing and column-restricted packing problems, Hardness and approximation results for packing Steiner trees, Finding edge-disjoint paths in networks: an ant colony optimization algorithm, Routing in Undirected Graphs with Constant Congestion
