Groupe d’études et de recherche en analyse des décisions

Maximum Cut & Spectra of Graphs

Dragan Stevanovic University of Nis, Serbie

The celebrated 0.878-approximation algorithm of Goemans & Williamson for the maximum cut problem was shown to be equivalent to an eigenvalue minimization problem by Delorme & Poljak. We present another eigenvalue minimization problem that defines a new upper bound on the size of the maximum cut and show that its particular case which uses a single eigenvector only yields a max-cut heuristic that is fast, simple and efficient in practice, well comparable in cut quality to state-of-the-art heuristics. The approximation guarantee of the new eigenvalue minimization problem is an open problem.