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 | |
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