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

Suliman Al-Homidan

The Max-Cut problem is an NP-hard problem [15]. 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.