<>Partitioning algorithms via semidefinite programming.
Assaf Naor, CIMS

In this talk we will survey recent results on the design of polynomial time approximation algorithms for a variety of partitioning problems using geometric methods. Such problems, including the Sparsest Cut problem, the MaxCut problem, the problem of constructing Szemeredi partitions, and certain clustering problems, are known to be NP hard. We therefore search for efficient algorithms which provide approximate solutions to these problems. It turns out that geometric methods based on semidefinite programming yield remarkably good approximation algorithms, and in some cases there is evidence that these algorithms perform the best among all possible polynomial time algorithms. <>