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 NPhard, one needs to resort to approximation. This talk will give a quick survey of techniques for graph partitioning, focusing on work in the past 78 years that uses semidefinite programming and spectral techniques.