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

Suliman Saleh Al-Homidan


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.

Full Text:



  • There are currently no refbacks.