×

CirCut

swMATH ID: 4782
Software Authors: Burer, Samuel; Monteiro, Renato D. C.; Zhang, Yin
Description: Rank-two relaxation heuristics for MAX-CUT and other binary quadratic programs 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.par 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.
Homepage: http://www.caam.rice.edu/~zhang/circut/
Keywords: binary quadratic programs; MAX-CUT and MAX-BISECTION; semidefinite relaxation; rank-two relaxation; continuous optimization heuristics
Related Software: SDPLR; Outward rotations; Biq Mac; Tabu search; COL; SDPT3; SeDuMi; BiqCrunch; DIMACS; SDPA; Max-AO; SDPpack; Rudy; SCIP; CPLEX; Benchmarks for Optimization Software; Scatter Search; NOA; LaGO; OR-Library
Cited in: 47 Documents
all top 5

Cited by 93 Authors

5 Hao, Jin-Kao
5 Xu, Chengxian
4 Xu, Fengmin
3 Burer, Samuel
3 Glover, Fred W.
3 Ling, Aifan
3 Monteiro, Renato D. C.
3 Wang, Yang
2 Festa, Paola
2 Krishnan, Kartik
2 Lü, Zhipeng
2 Luo, Zhi-Quan
2 Ma, Fuda
2 Nowak, Ivo
2 Pan, Shaohua
2 Pardalos, Panos M.
2 Rendl, Franz
2 Zhang, Yin
1 Adler, Ilan
1 Alperin, Hernán
1 Balasundaram, Balabhaskar
1 Bi, Shujun
1 Boros, Endre
1 Boumal, Nicolas
1 Butenko, Sergiy I.
1 Chang, Kung-Ching
1 Chen, Jein-Shan
1 De Santis, Marianna
1 Deng, Zhibin
1 Duarte, Abraham
1 Erementchouk, Mikhail
1 Fan, Neng
1 Fang, Shu-Cherng
1 Fischer, Ilse
1 Gruber, Gerald
1 Grygiel, Krzysztof
1 Hammer, Peter Ladislaw
1 He, Xiaoliang
1 Jiang, Yuxi
1 Kisialiou, Mikalai
1 Koch, Thorsten
1 Laguna, Manuel
1 Lee, Jon
1 Li, Guoquan
1 Li, Jingfan
1 Li, Xingsi
1 Lin, Geng
1 Liu, Wenlong
1 Liuzzi, Giampaolo
1 Lu, Cheng
1 Lucidi, Stefano
1 Martí, Rafael
1 Mazumder, Pinaki
1 Mitchell, John E.
1 Mu, Xuewen
1 Nobel, Parth
1 Qian, Yitian
1 Quan, Jing
1 Rehfeldt, Daniel
1 Resende, Mauricio G. C.
1 Ribeiro, Celso Carneiro
1 Rinaldi, Francesco
1 Rinaldi, Giovanni
1 Roychowdhury, Jaijeet
1 Sergiyenko, Ivan Vasyl’ovych
1 Shao, Sihong
1 Sherali, Hanif D.
1 Shinano, Yuji
1 Shukla, Aditya
1 Shylo, Oleg V.
1 Shylo, Vladimir P.
1 Śliwa, Izabela
1 Smith, J. Cole
1 Sotirov, Renata
1 Steinerberger, Stefan
1 Sun, Richard
1 Szlachetka, P.
1 Tan, Tao
1 Tavares, Gabriel
1 Terlaky, Tamás
1 Trick, Michael A.
1 Wang, Tianshi
1 Wiegele, Angelika
1 Wu, Jia
1 Wu, Leon
1 Wu, Qinghua
1 Wu, Zhiyou
1 Xia, Yong
1 Xing, Wenxun
1 Xu, Zi
1 Yildiz, Hakan
1 Zhang, Dong
1 Zhu, Wenxing

Citations by Year