Abstract
We give an O(n)-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 O(nlogD), 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.
Originalsprache | Englisch |
---|---|
Seiten (von - bis) | 156-160 |
Seitenumfang | 5 |
Fachzeitschrift | Information Processing Letters |
Jahrgang | 97 |
Ausgabenummer | 4 |
DOIs | |
Publikationsstatus | Veröffentlicht - 28 Feb. 2006 |
Extern publiziert | Ja |