***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Date: Thursday 4th October, 2.00 in Fine Hall 224
 
Speaker: Sanjeev Arora (Princeton)

Title: What have we learnt about graph partitioning?

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.

                       -----------

Next week: Hao Huang.

Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)