Name
Abstract | ||
|---|---|---|
The seminal paper of Leighton and Rao (1988) and subsequent papers presented approximate min-max theorems relating multicommodity flow values and cut capacities in undirected networks, developed the divide-and-conquer method for designing approximation algorithms, and generated novel tools for utilizing linear programming relaxations. Yet, despite persistent research efforts, these achievements could not be extended to directed networks,excluding a few cases that are "symmetric" and therefore similar to undirected networks. This paper is an attempt to remedy the situation. We consider the problem of finding a minimum multicut in a directed multicommodity flow network, and give the first nontrivial upper bounds on the max flow-to-min multicut ratio. Our results are algorithmic, demonstrating nontrivial approximation guarantees. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1007/s00493-005-0015-5 | Combinatorica |
Keywords | DocType | Volume |
linear programming relaxation,divide and conquer,multicommodity flow,upper bound | Journal | 25 |
Issue | ISSN | ISBN |
3 | 0209-9683 | 0-7695-1390-5 |
Citations | PageRank | References |
21 | 1.52 | 16 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| J. Cheriyan | 1 | 283 | 29.24 |
| Howard Karloff | 2 | 1673 | 195.13 |
| Yuval Rabani | 3 | 2265 | 274.98 |