TIME: 1:30-2:30 pm,  Tuesday, November 11, 2008

PLACE: CSE 503  

SPEAKER: Luca Trevisan
         UC Berkeley

TITLE: Max Cut and the Smallest Eigenvalue


ABSTRACT: 
We describe a new approximation algorithm for Max Cut.
Our algorithm runs in nearly quadratic time, and achieves
an approximation ratio of .531.

On instances in which an optimal solution cuts a $1-\epsilon$ fraction
of edges, our algorithm finds a solution that cuts a
$1-O(\epsilon^{1/2})-o(1)$ fraction of edges.
This is best possible up the constant in the big-Oh notation, assuming
the unique games conjecture.

On instances in which an optimal solution cuts a $1/2 + \epsilon$
fraction of edges, a related algorithm cuts a
$1/2 + exp(-\Omega(1/\epsilon))$ fraction of edges. (Algorithms
based on semidefinite programming are known to do considerably better.)

Our results rely on a variant of spectral partitioning, which can be
implemented in nearly linear time. Our analysis establishes a
relation between the smallest eigenvalue and a combinatorial
quantity, similarly to how Cheeger's inequality establishes
a relation between second eigenvalue and edge expansion.

Our algorithm is the first one to achieve an approximation better
than 1/2 for Max Cut by any means other than using a hyperplane to round
the solution to a semidefinite program.

A full paper is available online at http://arxiv.org/abs/0806.1978