swMATH ID: 4742
Software Authors: Busygin, Stanislav
Description: A new trust region technique for the maximum weight clique problem A new simple generalization of the Motzkin-Straus theorem for the maximum weight clique problem is formulated and directly proved. Within this framework a trust region heuristic is developed. In contrast to usual trust region methods, it regards not only the global optimum of a quadratic objective over a sphere, but also a set of other stationary points of the program. We formulate and prove a condition when a Motzkin-Straus optimum coincides with such a point. The developed method has complexity O(n 3 ), where n is the number of vertices of the graph. It was implemented in a publicly available software package QUALEX-MS. Computational experiments indicate that the algorithm is exact on small graphs and very efficient on the DIMACS benchmark graphs and various random maximum weight clique problem instances
Homepage: http://www.stasbusygin.org/
Keywords: maximum weight clique; Motzkin-Straus theorem; quadratic programming; heuristic; trust region
Related Software: DIMACS; Max-AO; Tabu search; BHOSLIB; GQTPAR; MaxCliqueDyn; EXTRACOL; Algorithm 787; HSL-VF05; Hyperheuristics; PMTK; gpuls-mwcp; CCLS; SCCWalk; BBMCSP; CCASat; NuMVC; H-Morph; G23FM; clusfind
Referenced in: 50 Publications
all top 5

Referenced by 88 Authors

8 Peng, Yuejian
7 Zhao, Cheng
6 Tang, Qingsong
5 Hao, Jin-Kao
4 Butenko, Sergiy I.
4 Wu, Qinghua
4 Zhang, Xiangde
3 Pardalos, Panos M.
3 Pullan, Wayne
2 Balasundaram, Balabhaskar
2 Busygin, Stanislav
2 Cai, Shaowei
2 Chang, Yanming
2 Glover, Fred W.
2 Pelillo, Marcello
1 Andonov, Rumen A.
1 Bai, Zhanhua
1 Bandyopadhyay, Sanghamitra
1 Barbosa, Valmir Carneiro
1 Bhattacharyya, Malay
1 Botella, Arnaud
1 Campos, Luciana C. D.
1 Caumon, Guillaume
1 Chen, Jiejiang
1 Cook, William John
1 Dang, Duc-Cuong
1 Fontes, Dalila B. M. M.
1 Geng, Xiutang
1 Goëffon, Adrien
1 Gomes, Fernando C.
1 Gould, Nicholas Ian Mark
1 Grosso, Andrea
1 Gruzdeva, Tat’yana Vladimirovna
1 Gu, Ran
1 Gualandi, Stefano
1 Gupta, Ashok Kumar
1 Gvozdenović, Nebojša
1 Hazan, Elad
1 Held, Stephan
1 Hicks, Illya V.
1 Hoos, Holger H.
1 Hosseinian, Seyedmohammadhossein
1 Koren, Tomer
1 Laurent, Monique
1 Letchford, Adam N.
1 Levi, Amit
1 Levy, Bruno
1 Li, Xueliang
1 Locatelli, Marco
1 Lu, Qiang
1 Lü, Zhipeng
1 Malod-Dognin, Noël
1 Malucelli, Federico
1 McClosky, Benjamin
1 Meneses, Cláudio N.
1 Montemanni, Roberto
1 Moukrim, Aziz
1 Pan, Linqiang
1 Pištěk, Miroslav
1 Rebennack, Steffen
1 Régin, Jean-Charles
1 Reinelt, Gerhard
1 Robinson, Daniel P.
1 Rossi, Fabrizio
1 Rota Bulò, Samuel
1 Sattar, Abdul
1 Sewell, Edward C.
1 Shi, Yongtang
1 Singh, Alok Kumar
1 Smith, Derek H.
1 Smriglio, Stefano
1 Su, Kaile
1 Sun, YanPing
1 Thorne, H. Sue
1 Torsello, Andrea
1 Trukhanov, Svyatoslav
1 Viana, Gerardo Valdisio R.
1 Wang, Guoren
1 Wang, Yang
1 Wang, Yiyuan
1 Xia, Xiaoyan
1 Xiao, Jianhua
1 Xu, Jin
1 Yanev, Nicola
1 Yao, Yuping
1 Yin, Minghao
1 Yoshida, Yuichi
1 Zhou, Yi

Referencing Publications by Year