Optimization and Systems Theory Seminar
Thursday, August 14, 1997, 15.00-16.00, Room 3721, Lindstedtsvägen 25

Professor Panos M. Pardalos
Center for Applied Optimization, ISE Department
University of Florida
Gainesville, FL 32611-6595, USA
E-mail: pardalos@ise.ufl.edu

Global optimization approaches for the maximum clique problem on general graphs

Given a graph G whose adjacency matrix is A, the Motzkin-Strauss formulation of the Maximum-Clique Problem is the quadratic program max x'Ax |x'e=1,x>= 0. Based on this formulation an efficient heuristic has been developed [1]. Furthermore, we study the quadratic program and provide polynomial time recognition algorithms for verifying if a given point is a first order point, a second order point, or a local maximum (for general quadratic programs these are NP-hard problems). Finally, a parametrization of the Motzkin-Strauss is introduced and an extension for the Motzkin-Strauss formulation is provided for the weighted clique number of a graph [2]. This work is part of our efforts to study continuous approaches for several discrete optimization problems [3,4].

[1] L. Gibbons, D. Hearn and P. M. Pardalos, A continuous based heuristic for the maximum clique problem, DIMACS Series Vol. 26 (D. S. Johnson and M. A. Trick, Editors), American Mathematical Society (1996), pp. 103-124.
[2] L. Gibbons, D. Hearn, P. M. Pardalos, and M. Ramana, A continuous characterization of the maximum clique problem To appear in Math. of Oper. Res. (1997).
[3] P. M. Pardalos, Continuous Approaches to Discrete Optimization Problems, In Nonlinear Optimization and Applications, G. Di Pillo & F. Giannessi, Ed., Plenum Publishing (1996), pp. 313-328.
[4] P. M. Pardalos and J. Xue, The maximum clique problem, Journal of Global Optimization, 4 (1994), pp. 301-328.

Calendar of seminars
Last update: August 5, 1997 by Anders Forsgren, andersf@math.kth.se.