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

Mohammad Taghi Hajiaghayi, Harald Räcke

Research output: Contribution to journalArticlepeer-review

17 Scopus citations

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.

Original languageEnglish
Pages (from-to)156-160
Number of pages5
JournalInformation Processing Letters
Volume97
Issue number4
DOIs
StatePublished - 28 Feb 2006
Externally publishedYes

Keywords

  • Approximation algorithms
  • Directed graphs
  • Multicommodity flow
  • Sparsest cut

Fingerprint

Dive into the research topics of 'An O(√n-approximation algorithm for directed sparsest cut'. Together they form a unique fingerprint.

Cite this