Journal article
Rank-Two Relaxation Heuristics for MAX-CUT and Other Binary Quadratic Programs
SIAM journal on optimization, Vol.12(2), pp.503-521
2002
DOI: 10.1137/S1052623400382467
Abstract
The Goemans--Williamson randomized algorithm guarantees a high-quality approximation to the MAX-CUT problem, but the cost associated with such an approximation can be excessively high for large-scale problems due to the need for solving an expensive semidefinite relaxation. In order to achieve better practical performance, we propose an alternative, rank-two relaxation and develop a specialized version of the Goemans--Williamson technique. The proposed approach leads to continuous optimization heuristics applicable to MAX-CUT as well as other binary quadratic programs, for example the MAX-BISECTION problem. A computer code based on the rank-two relaxation heuristics is compared with two state-of-the-art semidefinite programming codes that implement the Goemans--Williamson randomized algorithm, as well as with a purely heuristic code for effectively solving a particular MAX-CUT problem arising in physics. Computational results show that the proposed approach is fast and scalable and, more importantly, attains a higher approximation quality in practice than that of the Goemans--Williamson randomized algorithm. An extension to MAX-BISECTION is also discussed, as is an important difference between the proposed approach and the Goemans--Williamson algorithm; namely, that the new approach does not guarantee an upper bound on the MAX-CUT optimal value.
Details
- Title: Subtitle
- Rank-Two Relaxation Heuristics for MAX-CUT and Other Binary Quadratic Programs
- Creators
- Samuel Burer - Georgia Institute of TechnologyRenato D. C MonteiroYin Zhang
- Resource Type
- Journal article
- Publication Details
- SIAM journal on optimization, Vol.12(2), pp.503-521
- Publisher
- Society for Industrial and Applied Mathematics
- DOI
- 10.1137/S1052623400382467
- ISSN
- 1052-6234
- eISSN
- 1095-7189
- Language
- English
- Date published
- 2002
- Academic Unit
- Business Analytics
- Record Identifier
- 9984380471502771
Metrics
6 Record Views