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.