| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 428467 | Information Processing Letters | 2006 | 5 Pages |
Abstract
We give an -approximation algorithm for the Sparsest Cut Problem on directed graphs. A naïve reduction from Sparsest Cut to Minimum Multicut would only give an approximation ratio of , where D is the sum of the demands. We obtain the improvement using a novel LP-rounding method for fractional Sparsest Cut, the dual of Maximum Concurrent Flow.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
