Optimization Online


A New Trust Region Technique for the Maximum Weight Clique Problem

Stanislav Busygin (busygin***at***a-teleport.com)

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 new 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 graph vertices. It was implemented in a publicly available software package QUALEX-MS. Computational experiments evidence that the algorithm is exact on small graphs and exceptionally efficient on DIMACS benchmark graphs and various random maximum weight clique problem instances.

Keywords: maximum weight clique, continuous approach, Motzkin-Straus theorem, quadratic programming, heuristics, trust region, algorithms, NP-hard.

Category 1: Combinatorial Optimization (Graphs and Matroids )

Category 2: Combinatorial Optimization (Approximation Algorithms )

Citation: Submitted to Special Issue of Discrete Applied Mathematics: Combinatorial Optimization 2002.

Download: [Postscript][Compressed Postscript]

Entry Submitted: 01/16/2002
Entry Accepted: 01/16/2002
Entry Last Modified: 09/18/2002

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society