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

Amit Agarwal; Konstantin Makarychev; Moses Charikar; Yury Makarychev

doi:10.1145/1060590.1060675

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

Computer Science

Research output: Contribution to journal › Conference article › peer-review

128 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 language	English (US)
Pages (from-to)	573-581
Number of pages	9
Journal	Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs	https://doi.org/10.1145/1060590.1060675
State	Published - Dec 1 2005
Event	13th Color Imaging Conference: Color Science, Systems, Technologies, and Applications - Scottsdale, AZ, United States Duration: Nov 7 2005 → Nov 11 2005

Keywords

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

ASJC Scopus subject areas

Software

Access to Document

10.1145/1060590.1060675

Cite this

@article{51fe339ce4fd4ceeb0ad681cf8a4fa23,

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

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).",

keywords = "Directed Balanced Separator, Directed Sparsest Cut, Min 2CNF Deletion, Min Multicut, Min UnCut",

author = "Amit Agarwal and Konstantin Makarychev and Moses Charikar and Yury Makarychev",

year = "2005",

month = dec,

day = "1",

doi = "10.1145/1060590.1060675",

language = "English (US)",

pages = "573--581",

journal = "Proceedings of the Annual ACM Symposium on Theory of Computing",

issn = "0737-8017",

publisher = "Association for Computing Machinery (ACM)",

note = "13th Color Imaging Conference: Color Science, Systems, Technologies, and Applications ; Conference date: 07-11-2005 Through 11-11-2005",

}

TY - JOUR

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

AU - Agarwal, Amit

AU - Makarychev, Konstantin

AU - Charikar, Moses

AU - Makarychev, Yury

PY - 2005/12/1

Y1 - 2005/12/1

N2 - 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).

AB - 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).

KW - Directed Balanced Separator

KW - Directed Sparsest Cut

KW - Min 2CNF Deletion

KW - Min Multicut

KW - Min UnCut

UR - http://www.scopus.com/inward/record.url?scp=34848857660&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=34848857660&partnerID=8YFLogxK

U2 - 10.1145/1060590.1060675

DO - 10.1145/1060590.1060675

M3 - Conference article

AN - SCOPUS:34848857660

SP - 573

EP - 581

JO - Proceedings of the Annual ACM Symposium on Theory of Computing

JF - Proceedings of the Annual ACM Symposium on Theory of Computing

SN - 0737-8017

T2 - 13th Color Imaging Conference: Color Science, Systems, Technologies, and Applications

Y2 - 7 November 2005 through 11 November 2005

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this