Optimization and Systems Theory Seminar
Thursday, August 14, 1997, 15.00-16.00, Room 3721, Lindstedtsvägen 25
Professor Panos M.
Center for Applied Optimization, ISE Department
University of Florida
Gainesville, FL 32611-6595, USA
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 . 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
. This work is part of our efforts to study continuous
approaches for several discrete optimization problems [3,4].
 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.
 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).
 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.
 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