Title: O(\sqrt{log n}) approximation algorithms for Min UnCut, Min 2CNF Deletion, and directed cut problems
Speaker: Yury Makarychev, Princeton University
Date: March 8, 2005 2:00-3:00pm
Location: DIMACS Center, CoRE Bldg, Room 433, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
We give $O(\sqrt{\log n})$-approximation 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, Directed Balanced Separator, Directed Sparsest Cut, and an $O(\log n \log\log n)$-approximation for Min 2CNF Deletion.
We also show that the integrality gap of an SDP relaxation of the Minimum Multicut problem is $\Omega(\log n)$.
Joint work with Amit Agarwal, Moses Charikar, Konstantin Makarychev