### 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.
*