What have we learned about graph partitioning?

What have we learned about graph partitioning?

-
Sanjeev Arora, Princeton University
Fine Hall 224

The graph partitioning problem consists of cutting a graph into two or more large pieces so as to minimize the number of edges between them. Since the problem is NP-hard, one needs to resort to approximation. This talk will give a quick survey of techniques for graph partitioning, focusing on work in the past 7-8 years that uses semidefinite programming and spectral techniques.