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