Article: Dynamic Local Search for the Maximum Clique Problem

[jai...@ptolemy.arc.nasa.gov]

JAIR is pleased to announce the publication of the following article:

Pullan, W. and Hoos, H.H. (2006)
"Dynamic Local Search for the Maximum Clique Problem",
Volume 25, pages 159-185.

For quick access via your WWW browser, use this URL:
http://www.jair.org/abstracts/pullan06a.html

Abstract:
In this paper, we introduce DLS-MC, a new stochastic local search algorithm
for the maximum clique problem. DLS-MC alternates between phases of iterative
improvement, during which suitable vertices are added to the current clique,
and plateau search, during which vertices of the current clique are swapped
with vertices not contained in the current clique. The selection of vertices
is solely based on vertex penalties that are dynamically adjusted during the
search, and a perturbation mechanism is used to overcome search stagnation.
The behaviour of DLS-MC is controlled by a single parameter, penalty delay,
which controls the frequency at which vertex penalties are reduced.
We show empirically that DLS-MC achieves substantial performance
improvements over state-of-the-art algorithms for the maximum clique problem
over a large range of the commonly used DIMACS benchmark instances.

The article is available via:

-- comp.ai.jair.papers (also see comp.ai.jair.announce)

-- World Wide Web: The URL for our World Wide Web server is
http://www.jair.org/
For direct access to this article and related files try:
http://www.jair.org/abstracts/pullan06a.html

-- Anonymous FTP from Carnegie-Mellon University (USA):
ftp://ftp.cs.cmu.edu/project/jair/volume25/pullan06a.ps
The compressed PostScript file is named pullan06a.ps.Z

For more information about JAIR, visit our WWW or FTP sites, or
contact jai...@isi.edu

--
Steven Minton
JAIR Managing Editor