Stevanović, Dragan; Matematični kolokvij januar 2007

Iz MaFiRaWiki

Maximum Cut & Spectra of Graphs

Dragan Stevanović

Univerza v Nišu, Srbija

11. januar 2007

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.

Glej tudi

Matematični kolokviji

Osebna orodja