Improved approximation for directed cut problems

Amit Agarwal, Noga Alon, Moses S. Charikar

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

31 Scopus citations

Abstract

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
Pages671-680
Number of pages10
DOIs
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

Other

OtherSTOC'07: 39th Annual ACM Symposium on Theory of Computing
CountryUnited States
CitySan Diego, CA
Period6/11/076/13/07

All Science Journal Classification (ASJC) codes

  • Software

Keywords

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

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

  • Cite this

    Agarwal, A., Alon, N., & Charikar, M. S. (2007). Improved approximation for directed cut problems. In STOC'07: Proceedings of the 39th Annual ACM Symposium on Theory of Computing (pp. 671-680). (Proceedings of the Annual ACM Symposium on Theory of Computing). https://doi.org/10.1145/1250790.1250888