%0 Journal Article %1 Busygin2006New %A Busygin, S %D 2006 %J Discret. Appl. Math. %K clique graph weight phd schemdesc %N 15 %P 2080--2096 %R http://dx.doi.org/10.1016/j.dam.2005.04.010 %T A new trust region technique for the maximum weight clique problem %U http://dx.doi.org/10.1016/j.dam.2005.04.010 %V 154 %X 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.

@article{Busygin2006New, abstract = {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.}, added-at = {2013-12-17T09:48:27.000+0100}, author = {Busygin, S}, biburl = {https://www.bibsonomy.org/bibtex/2a39f60fd322039ee0a8dd05936cb932d/jullybobble}, doi = {http://dx.doi.org/10.1016/j.dam.2005.04.010}, interhash = {c3de9b3c6b287106a82064c9ba18dff2}, intrahash = {a39f60fd322039ee0a8dd05936cb932d}, issn = {0166218X}, journal = {Discret. Appl. Math.}, keywords = {clique graph weight phd schemdesc}, month = oct, number = 15, pages = {2080--2096}, timestamp = {2014-07-27T15:43:19.000+0200}, title = {{A new trust region technique for the maximum weight clique problem}}, url = {http://dx.doi.org/10.1016/j.dam.2005.04.010}, volume = 154, year = 2006 }