Maximum cut

Maximum cut

Introduction

Published in Joseph Y.-T. Leung, Handbook of SCHEDULING, 2004

[3] M. Goemans and D. P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM, 42:1115-1145,1995.

ADMM for multiaffine constrained optimization

View Article

Journal Information

Published in Optimization Methods and Software, 2020

Wenbo Gao, Donald Goldfarb, Frank E. Curtis

Given a graph and edge weights , the (weighted) maximum cut problem is to find a subset so that is maximized. This problem is well known to be NP-hard [30]. An approximation algorithm using semidefinite programming can be shown to achieve an approximation ratio of roughly 0.878 [22]. Applying the Burer–Monteiro approach [7] to the max-cut semidefinite program [22] with a rank-one constraint, and introducing a slack variable (see 4.1.2), we obtain the problem It is easy to verify that all subproblems have very simple closed-form solutions.

Explore chapters and articles related to this topic

Introduction

ADMM for multiaffine constrained optimization