DIMACS Theoretical Computer Science Seminar

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


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