Global Convergence of the Alternating Projection Method for the Max-Cut Relaxation Problem

Abstract

The Max-Cut problem is an NP-hard problem. Extensions of von Neumann's alternating projections method permit the computation of proximity projections onto convex sets. The present paper exploits this fact by constructing a globally convergent method for the Max-Cut relaxation problem. The feasible set of this relaxed Max-Cut problem is the set of correlation matrices, hence the correlation problem is also considered.