Title: O(\sqrt{log n}) approximation algorithms for Min UnCut, Min 2CNF  
Deletion, and directed cut problems

Speaker: Yury Makarychev, Princeton Univ.

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