Loading...
Please wait, while we are loading the content...
Similar Documents
Approximate Max--ow Min-(multi)cut Theorems and Their Applications
| Content Provider | Semantic Scholar |
|---|---|
| Author | Garg, Naveen Vazirani, Vijay V. Yannakakis, Mihalis |
| Copyright Year | 1993 |
| Abstract | Consider the multicommodity ow problem in which the object is to maximize the sum of commodities routed. We prove the following approximate max-ow min-multicut theorem: min multicut O(log k) max ow min multicut; where k is the number of commodities. Our proof is constructive; it enables us to nd a multicut within O(log k) of the max ow (and hence also the optimal multicut). In addition, the proof technique provides a uniied framework in which one can also analyse the case of ows with speciied demands, of Leighton-Rao and Klein et.al., and thereby obtain an improved bound for the latter problem. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.cc.gatech.edu/fac/Vijay.Vazirani/multicut.ps |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
