# Accession Number:

## ADA254048

# Title:

## Fast Approximation Algorithms for Multicommodity Flow Problems

# Descriptive Note:

# Corporate Author:

## STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

# Personal Author(s):

# Report Date:

## 1991-08-01

# Pagination or Media Count:

## 27.0

# Abstract:

In this paper, we describe the first polynomial-time combinatorial algorithms for approximately solving the multicommodity flow problem. Our algorithms are significantly faster than the best previously known algorithms, that were based on linear programming. For a k-commodity multicommodity flow problem, the running time of our randomized algorithm is up to log factors the same as the time needed to solve k single-commodity flow problems, thus giving the surprising result that approximately computing a k-commodity maximum-flow is not much harder than computing about k single-commodity maximum-flows iii isolation. Given any multicommodity flow problem as input, our algorithm is guaranteed to provide a feasible solution to a modified flow problem in which all capacities are increased by a 1 e-factor, or to provide a proof that there is no feasible solution to the original problem. We also describe faster approximation algorithms for multicommodity flow problems with a special structure, such as those that arise in the sparsest cut problems and the uniform concurrent flow problems if k or - m.

# Descriptors:

# Subject Categories:

- Numerical Mathematics
- Operations Research