Approximating Directed Multicuts |
| |
Authors: | Joseph Cheriyan Howard Karloff Yuval Rabani? |
| |
Institution: | (1) Department of Combinatorics and Optimization Waterloo, University of Waterloo, Ontario, N2L 3G1, Canada;(2) AT&T Labs–Research, 180 Park Ave., Florham Park, NJ 07932, USA;(3) Computer Science Department Technion—IIT, Haifa 32000, Israel |
| |
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.* Supported in part by NSERC research grant OGP0138432. Part of this work was done while visiting AT&T Labs–Research. Work at the Technion supported by Israel Science Foundation grant number 386/99, by BSF grants 96-00402 and 99-00217, by Ministry of Science contract number 9480198, by EU contract number 14084 (APPOL), by the CONSIST consortium (through the MAGNET program of the Ministry of Trade and Industry), and by the Fund for the Promotion of Research at the Technion. |
| |
Keywords: | 05C20 05C85 68W25 90C27 |
本文献已被 SpringerLink 等数据库收录! |
|