Rank-Two Relaxation Heuristics for Max-Cut and Other Binary Quadratic Programs

@techreport{citeulike:1632669, 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...}, address = {Atlanta, GA}, author = {Burer, S. and Monteiro, R. D. C. and Zhang, Y. }, citeulike-article-id = {1632669}, comment = {intro to SDP relaxation for max-cut, rank-2 relaxation non-convex but efficient, references to Ising literature ---=note-separator=--- application of max-cut to Ising ground-state problem}, posted-at = {2007-09-07 23:21:47}, priority = {2}, title = {Rank-Two Relaxation Heuristics for Max-Cut and Other Binary Quadratic Programs}, url = {http://citeseer.ist.psu.edu/burer00ranktwo.html}, year = {2000} }

TY - RPRT ID - citeulike:1632669 L3 - citeulike-article-id:1632669 TI - Rank-Two Relaxation Heuristics for Max-Cut and Other Binary Quadratic Programs AD - Atlanta, GA N2 - 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... N1 - intro to SDP relaxation for max-cut, rank-2 relaxation non-convex but efficient, references to Ising literature N1 - application of max-cut to Ising ground-state problem AU - Burer, S AU - Monteiro, RDC AU - Zhang, Y PY - 2000/// UR - http://citeseer.ist.psu.edu/burer00ranktwo.html ER -