Jose´ Neto

Title:
Spectral bounds for the max-cut problem

Abstract:
The max-cut is a classical combinatorial optimization problem that
is known to be NP-hard in general. A significant breakthrough was
done in the 90's by Goemans and Williamson who introduced an
0.878-approximation algorithm that is based on a SDP formulation
of the problem. The latter formulation provides the same upper bound
as an eigenvalue optimization problem introduced earlier by Delorme
and Poljak.

We introduce upper bounds for the maximum cut problem that are based
on the spectrum of the weight matrix with modified diagonal entries
and that generally improve on the one provided by the classical SDP
formulation. We discuss on the complexity of computing these bounds
and give some preliminary computational results.

This is a joint work with Walid Ben-Ameur.