Approximation Algorithms for Disjoint Paths and Related Routing and Packing Problems
From MaRDI portal
Publication:2757635
DOI10.1287/moor.25.2.255.12228zbMath0977.90069OpenAlexW1974115975MaRDI 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 programminginteger programmingpackingapproximation algorithmsrandomized algorithmsroutingmulticommodity flowroundingdisjoint pathsunsplittable flow
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25)
Related Items (14)
Hardness and approximation results for packing Steiner trees ⋮ Solving the edge‐disjoint paths problem using a two‐stage method ⋮ Approximating covering integer programs with multiplicity constraints ⋮ Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs ⋮ LS(graph): a constraint-based local search for constraint optimization on trees and paths ⋮ Finding edge-disjoint paths in networks: an ant colony optimization algorithm ⋮ Disjoint paths in sparse graphs ⋮ Minimal multicut and maximal integer multiflow: a survey ⋮ Routing in Undirected Graphs with Constant Congestion ⋮ A note on the greedy algorithm for the unsplittable flow problem ⋮ Flows with unit path capacities and related packing and covering problems ⋮ A logarithmic approximation for unsplittable flow on line graphs ⋮ Flows with Unit Path Capacities and Related Packing and Covering Problems ⋮ Approximating low-congestion routing and column-restricted packing problems
This page was built for publication: Approximation Algorithms for Disjoint Paths and Related Routing and Packing Problems
