O(√log n) approximation algorithms for Min UnCut, Min 2CNF Deletion, and Directed Cut problems

Amit Agarwal*, Konstantin Makarychev, Moses Charikar, Yury Makarychev

*Corresponding author for this work

Research output: Contribution to journalConference articlepeer-review

112 Scopus citations

Abstract

We give O(√log n)-approxiniation algorithms for the MIN UNCUT, MIN 2CNF DELETION, DIRECTED BALANCED SEPARATOR, and DIRECTED SPARSEST CUT problems. The previously best known algorithms give an O(log n)-approximation for MIN UNCUT [9], DIRECTED BALANCED SEPARATOR [17], DIRECTED SPARSEST CUT [17], and an O(log n log log n)-approximation for MIN 2CNF DELETION [14]. We also show that the integrality gap of an SDP relaxation of the MINIMUM MULTICUT problem is Ω(log n).

Original languageEnglish (US)
Pages (from-to)573-581
Number of pages9
JournalProceedings of the Annual ACM Symposium on Theory of Computing
DOIs
StatePublished - Dec 1 2005
Event13th Color Imaging Conference: Color Science, Systems, Technologies, and Applications - Scottsdale, AZ, United States
Duration: Nov 7 2005Nov 11 2005

Keywords

  • Directed Balanced Separator
  • Directed Sparsest Cut
  • Min 2CNF Deletion
  • Min Multicut
  • Min UnCut

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'O(√log n) approximation algorithms for Min UnCut, Min 2CNF Deletion, and Directed Cut problems'. Together they form a unique fingerprint.

Cite this