A new trust region technique for the maximum weight clique problem |
| |
Authors: | Stanislav Busygin |
| |
Institution: | Department of Industrial and Systems Engineering, University of Florida, 303 Weil Hall, Gainesville, FL 32611, USA |
| |
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(n3), 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. |
| |
Keywords: | Maximum weight cliquel Motzkin-Straus theorem Quadratic programming Heuristic Trust region |
本文献已被 ScienceDirect 等数据库收录! |
|