Computational Approaches to Max-Cut

The chapter describes the most successful and most recent algorithms, based on semidefinite programming, for the exact and the heuristic solution of max-cut and related problems, like max-k-cut, coloring, and quadratic ordering.