An O(√n-approximation algorithm for directed sparsest cut

Mohammad Taghi Hajiaghayi, Harald Räcke

Publikation: Beitrag in FachzeitschriftArtikelBegutachtung

17 Zitate (Scopus)

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.

OriginalspracheEnglisch
Seiten (von - bis)156-160
Seitenumfang5
FachzeitschriftInformation Processing Letters
Jahrgang97
Ausgabenummer4
DOIs
PublikationsstatusVeröffentlicht - 28 Feb. 2006
Extern publiziertJa

Fingerprint

Untersuchen Sie die Forschungsthemen von „An O(√n-approximation algorithm for directed sparsest cut“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren