Improved approximation for directed cut problems

Amit Agarwal, Noga Alon, Moses S. Charikar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

37 Scopus citations


We present improved approximation algorithms for directed multicutand directed sparsest cut. The current best known approximationratio for these problems is O(n1/2). We obtain an (n11/23)-approximation. Our algorithm works with thenatural LP relaxation used in prior work. We use a randomized roundingalgorithm with a more sophisticated charging scheme and analysis toobtain our improvement. This also implies a (n11/23) upper bound on the ratio between the maximum multicommodity flowand minimum multicut in directed graphs.

Original languageEnglish (US)
Title of host publicationSTOC'07
Subtitle of host publicationProceedings of the 39th Annual ACM Symposium on Theory of Computing
Number of pages10
StatePublished - 2007
Externally publishedYes
EventSTOC'07: 39th Annual ACM Symposium on Theory of Computing - San Diego, CA, United States
Duration: Jun 11 2007Jun 13 2007

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017


OtherSTOC'07: 39th Annual ACM Symposium on Theory of Computing
Country/TerritoryUnited States
CitySan Diego, CA

All Science Journal Classification (ASJC) codes

  • Software


  • Approximation algorithm
  • Directed multicut
  • Directed sparsest cut
  • Linear programming relaxation


Dive into the research topics of 'Improved approximation for directed cut problems'. Together they form a unique fingerprint.

Cite this