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

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