%hh-final: final revisions / corrections (all marked hh5 except typos)

\documentstyle[jair,twoside,11pt,theapa,graphicx,supertab,url]{article}
\input epsf %% at top of file
\ShortHeadings{Dynamic Local Search for Max-Clique Problem}{Pullan \& Hoos}
%\firstpageno{1}
\begin{document}
\jairheading{25}{2006}{159-185}{5/05}{2/06}
\firstpageno{159}
\title{Dynamic Local Search for the Maximum Clique Problem}
\author{\name Wayne Pullan \email w.pullan@griffith.edu.au\\
       \addr School of Information and Communication Technology,\\
       Griffith University,\\
       Gold Coast, QLD, Australia       \AND
       \name Holger H. Hoos \email hoos@cs.ubc.ca \\
       \addr Department of Computer Science	\\
       University of British Columbia \\
       2366 Main Mall, Vancouver, BC, V6T 1Z4 Canada}

% For research notes, remove the comment character in the line below.
% \researchnote

\maketitle
% some useful general macros:
\newcommand{\hide}[1]{}
\newcommand{\cmnt}[1]{{[\bf #1]}}
\newcommand{\draft}[1]{{\it #1}}
\newcommand{\ie}{{\it{}i.e.\/}}
\newcommand{\eg}{{\it{}e.g.\/}}
\newcommand{\cf}{{\it{}cf.\/}}
\newcommand{\wrt}{\mbox{w.r.t.}}
\newcommand{\vs}{{\it{}vs\/}}
\newcommand{\etc}{{\it{}etc.\/}}
% specific macros used for this paper:
\newcommand{\dls}{DLS-MC}
\addtolength{\abovecaptionskip}{-10in}
\addtolength{\belowcaptionskip}{-10in}
\begin{abstract}
\noindent
%In this paper, a new dynamic stochastic local search algorithm, \dls{}, for
%the maximum clique problem is introduced. 
%hh5: minor rewording:
In this paper, we introduce \dls{}, a new stochastic local search algorithm 
for the maximum clique problem.
\dls{} 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{} is controlled by a single parameter, penalty delay, 
which controls the frequency at which vertex penalties are reduced. 
We show empirically that \dls{} 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.
\end{abstract}
\section{Introduction}
\label{intro}

%[brief intro to MAX-CLIQUE, applications, complexity]

The maximum clique problem (MAX-CLIQUE) calls for finding the maximum sized sub-graph of pairwise adjacent vertices in a given graph. MAX-CLIQUE is a prominent combinatorial optimisation
problem with many applications, for example,  information retrieval, experimental design, signal transmission and computer vision \cite{BalYu86}. More recently, applications in 
bioinformatics have become important \cite{PevSze03,JiXuSto04}.
%hh5: <- moved references to end of sentence.
% http://bioinformatics.oupjournals.org/cgi/content/abstract/20/10/1591
% http://portal.acm.org/citation.cfm?id=660985
%hh: maybe useful later:
%interesting application of edge-weighted max clique: Protein side-chain packing 
%http://portal.acm.org/citation.cfm?id=976546
The search variant of MAX-CLIQUE can be stated as follows:
Given an undirected graph $G = (V,E)$, where $V$ is the set of all vertices and $E$ the set of all edges, find a maximum size clique
in $G$, where a clique in $G$ is a subset of vertices, $C \subseteq V$,
such that all pairs of vertices in $C$ are connected by an edge,
\ie{}, for all $v,v' \in C$, $\{v,v'\} \in E$,
and the size of a clique $C$ is the number of vertices in $C$.
MAX-CLIQUE is ${\cal NP}$-hard and the associated decision problem
is ${\cal NP}$-complete \cite{GarJoh79}; 
furthermore, it is inapproximable 
in the sense that no deterministic polynomial-time algorithm
can find cliques of size $|V|^{1-\epsilon}$ 
for any $\epsilon > 0$, unless ${\cal NP=ZPP}$ \cite{Hastad96}.\footnote{
${\cal ZPP}$ is the class of problems that
can be solved in expected polynomial time by a probabilistic
algorithm with zero error probability.}
The best polynomial-time approximation algorithm 
for MAX-CLIQUE achieves an approximation ratio of 
$O(|V|/(\log |V|)^2)$ \cite{BopHal92}.
% http://www.nada.kth.se/~viggo/wwwcompendium/node33.html
Therefore, large and hard instances of 
MAX-CLIQUE are typically solved using 
heuristic approaches, in particular, 
greedy construction algorithms and stochastic local search (SLS) algorithms such 
as simulated annealing, genetic algorithms and tabu search.
(For an overview of these and other methods for solving 
MAX-CLIQUE, see \citeR{BomEtAl99}.)
It may be noted that the maximum clique problem is equivalent to the 
independent set problem as well as to the minimum vertex cover
problem,
%(where the objective is to 
%find a maximum size set of vertices, $I \subseteq V$,
%such that there is no edge between any pair of vertices $I$),
and any algorithm for MAX-CLIQUE can be directly applied to these
equally fundamental and application relevant problems \cite{BomEtAl99}.

%hh2: new - mainly based on description in DAGS paper:
%[brief overview of recent work / state-of-the-art in MAX-CLIQUE solving]
From the recent literature on MAX-CLIQUE algorithms, 
it seems that, somewhat unsurprisingly, there is no single best algorithm.
Although most algorithms have been empirically evaluated on benchmark instances
from the Second DIMACS Challenge \cite{JohTri96}, it is quite difficult
to compare experimental results between studies, mostly because
of differences in the respective experimental protocols and run-time environments.
Nevertheless, particularly considering the comparative results reported by Grosso \emph{et al.}
\cite{GroLocDel04}, it seems that there are five heuristic MAX-CLIQUE algorithms
that achieve state-of-the-art performance.

\emph{Reactive Local Search (RLS)} \cite{BatPro01} has been derived from Reactive
Tabu Search \cite{BatTec94}, an advanced and general tabu search method
that automatically adapts the tabu tenure parameter
(which controls the amount of diversification) during the search process;
RLS also uses a dynamic restart strategy to provide additional long-term diversification.

%hh5: added 'deterministic':
\emph{QUALEX-MS} \cite{Busygin02} is a deterministic iterated greedy construction algorithm
that uses vertex weights derived from a nonlinear programming formulation 
of MAX-CLIQUE.
%hh2: <- check this against Busygin02 and modify if necessary

The more recent \emph{Deep Adaptive Greedy Search (DAGS)} algorithm \cite{GroLocDel04} also uses
an iterated greedy construction procedure with vertex weights;
the weights in DAGS, however, are initialised uniformly
and updated after every iteration of the greedy construction procedure.
In DAGS, this weighted iterated greedy construction procedure is
executed after an iterative improvement phase that permits a limited amount
of plateau search. Empirical performance results indicate that DAGS
is superior to QUALEX-MS for most of the MAX-CLIQUE instances from 
the DIMACS benchmark sets, but 
for some hard instances it does not reach the performance of RLS \cite{GroLocDel04}.

The \emph{$k$-opt} algorithm \cite{KatEtAl04} is based
on a conceptually simple variable depth search procedure that uses
%hh-final: removed abbreviation VDS (used nowhere else in the paper)
elementary search steps in which a vertex is added to or removed from
the current clique; while there is some evidence that it performs better than
RLS on many instances from the DIMACS benchmark sets \cite{KatEtAl04}, its
performance relative to DAGS is unclear.

Finally, \emph{Edge-AC+LS} \cite{SolFen04}, a recent ant colony optimisation
algorithm for MAX-CLIQUE that uses an elitist subsidiary local search procedure, 
appears to reach (or exceed) the performance of DAGS and RLS on at least some
of the DIMACS instances.

\hide{
DAGS
(according to GroLocDel04, state-of-the-art on most types of hard MC instances)

k-opt
(according to KatEtAl04, better than RLS on many instances; rel performance against DAGS
	unclear because of differences in test sets and exp protocols between KatEtAl04, GroLocDel04)

RLS
(according to GroLocDel04, superior to DAGS on some hard random and structured instances)

QUALEX-MS
(according to GroLocDel04, inferior to DAGS on most tested instances, except some easier ones)

ACO: Edge-AC+LS
(according to SolFen04, comparable or better than DAGS, RLS on some DIMACS instances)

GRASP
(appears to be dominated by DAGS)
}%

%[contributions made here - approach followed, brief summary of main results]
In this work, we introduce a new SLS algorithm
for MAX-CLIQUE algorithm dubbed Dynamic Local Search -- Max Clique, \dls{},
which is based on a combination of constructive search and perturbative local 
search, and makes use of penalty values associated with the vertices
of the graph, which are dynamically determined during the search
and help the algorithm to avoid search stagnation.

Based on extensive computational experiments, we show that \dls{}
outperforms other state-of-the-art MAX-CLIQUE search algorithms,
%hh2: added:
in particular DAGS, 
on a broad range of widely studied benchmark instances,
and hence represents an improvement 
in heuristic MAX-CLIQUE solving algorithms.
We also present detailed results on the behaviour of \dls{}
and offer insights into the roles of its single parameter and 
the dynamic vertex penalties.
% [mention other DLS recent algorithms for other problems, in particular SAT / MAX-SAT]
We note that the use of vertex penalties in \dls{}
%hh2: changed:
is inspired by the dynamic weights in DAGS
and, more generally,
by current state-of-the-art Dynamic Local Search (DLS) algorithms for 
other well-known combinatorial problems, such as 
SAT and MAX-SAT \cite{saps-sat,saps-maxsat,paws,resls};
for a general introduction to DLS, see also the work of \cite{HooStu04}.
Our results therefore provide further evidence for
the effectiveness and broad applicability of this 
algorithmic approach.

%[structure of paper]
The remainder of this article is structured as follows.
We first describe the \dls{} algorithm and key aspects
of its efficient implementation.
Next, we present empirical performance results
that establish \dls{} as the new state-of-the-art
in heuristic MAX-CLIQUE solving.
This is followed by a more detailed investigation
of the behaviour of \dls{} and the factors determining 
its performance.
Finally, we summarise the main contributions of this work,
insights gained from our study and outline some 
directions for future research.


\section{The \dls{} Algorithm}
\label{alg}

%hh2: new - but we may want to include more reference to earlier algorithms that use similar mechanisms
%	(e.g., plateau search):
% [motivation: DAGS, etc.]
Like the DAGS algorithm by Grosso \emph{et al.}, our new \dls{} algorithm
is based on the fundamental idea of augmenting a combination of 
iterative improvement and plateau search with vertex penalties that are modified 
during the search.
The iterative improvement procedure used by both algorithms
is based on a greedy construction mechanism that starts with 
a trivial clique consisting of a single vertex and successively expands 
this clique $C$ by adding vertices that are adjacent to all vertices in $C$.
When such an expansion is impossible, there may still exist vertices that are connected 
to all but one of the vertices
in $C$. By including such a vertex $v$ in $C$ and removing
the single vertex in $C$ not connected to $v$, a new
clique with the same number of vertices can be obtained.
This type of search is called \emph{plateau search}.
It should be noted that after one or more plateau search steps,
further expansion of the current clique may become possible; therefore,
\dls{} alternates between phases of expansion and plateau search.

The purpose of vertex penalties is to provide additional diversification
to the search process, which otherwise could easily stagnate 
in situations where the current clique has few or no vertices 
in common with an optimal solution to a given MAX-CLIQUE instance.
Perhaps the most obvious approach for avoiding this kind of search 
stagnation is to simply restart the constructive search process from
a different initial vertex. However, even if there is random
(or systematic) variation in the choice of this initial vertex,
there is still a risk that the heuristic guidance built into
the greedy construction mechanism 
%leads to 
%hh5: minor rewording:
causes
a bias towards a limited set of suboptimal cliques. Therefore, both DAGS and \dls{}
%hh-final: use -> utilise (since 'use' also appears later in sentence)
utilise
numerical weights associated with the vertices;
%hh-final: slightly reworded (sentence was overly complex):
these weights modulate
the heuristic selection function used in the greedy construction
procedure in such a way that vertices that repeatedly
occur in the cliques obtained from the constructive search process
are discouraged from being used in future constructions.
Following this intuition, and consistent with the general
approach of dynamic local search (DLS), which is based on the 
same idea, in this paper, we refer to the numerical weights
as \emph{vertex penalties}.

\hide{hh3: Originally, I tried to say something about the differences between
 \dls{} and DAGS (see hidden fragments in the source), but I couldn't find a good way of integrating it into 
	the flow of the paper. I've now decided to put this into the conclusions,
	but I am not convinced this is the best solution.}

\hide{
Although \dls{} has been partly inspired by DAGS and shares
important features with this existing state-of-the-art algorithm
for MAX-CLIQUE, there are important conceptual and technical differences, which
will be discussed in Section~\ref{s:discussion}. 

...

However, unlike DAGS, which has an initial phase of unweighted greedy construction search,
\dls{} uses and updates the vertex penalties throughout the entire search process,
}

% [DLS description and outline]
Based on these general considerations, the \dls{} algorithm works as follows
(see also the algorithm outline in Figure~\ref{fig:dls}):
After picking an initial vertex from the given graph $G$
uniformly at random and setting the current clique $C$ to
the set consisting of this single vertex,
all vertex penalties
are initialised to zero. Then, the search alternates
between an iterative improvement phase,
during which suitable vertices are repeatedly 
added to the current clique $C$,
and a plateau search phase, in which
repeatedly one vertex of $C$ is swapped with a vertex currently not contained in $C$.

%hh: change expand -> improve?

The two subsidiary search procedures implementing
the iterative improvement and plateau search phases,
\emph{expand} and \emph{plateauSearch},
are shown in Figure~\ref{fig:procs}.
Note that both, \emph{expand} and \emph{plateauSearch}
select the vertex to be added to the current clique $C$
using only the penalties associated with all candidate vertices.
In the case of \emph{expand}, the selection is made from
the set $N_I(C)$ of all vertices that are connected
to all vertices in $C$ by some edge in $G$; 
we call this set 
the \emph{improving neighbour set of $C$}.
In \emph{plateauSearch}, on the other hand,
the vertex to be added to $C$ is selected
from the \emph{level neighbour set of $C$},
$N_L(C)$, which comprises the vertices that are
connected to all vertices in $C$ except for one
vertex, say $v'$, which is subsequently removed 
from $C$.

Note that both procedures always maintain a current clique $C$;
\emph{expand} terminates when the improving neighbour set of
$C$ becomes empty, while \emph{plateauSearch}
terminates when either $N_I(C)$ is no longer empty or when
$N_L(C)$ becomes empty.
Also, in order to reduce the incidence of unproductive plateau search phases, 
\dls{} implements the plateau search termination condition
 of \cite{KatEtAl04} by recording
the current clique ($C'$) at the start of the plateau search phase and terminating 
\emph{plateauSearch} when there is no overlap between
the recorded clique $C'$ and the current clique $C$.

At the end of the plateau search phase, the vertex penalties are updated
by incrementing the penalty values of all vertices in the current clique, $C$, 
by one.
Additionally, every \emph{pd} penalty value update cycles (where \emph{pd} is 
a parameter called \emph{penalty delay}), 
all non-zero vertex penalties are decremented by one.
This latter mechanism prevents penalty values from becoming
too large and allows \dls{} to `forget' penalty values
over time.

After updating the penalties, the current clique is perturbed 
in one of two ways.
If the penalty delay is greater than one, \ie{}, penalties 
are only decreased occasionally, 
the current clique is reduced to the last vertex $v$ that was added
to it. Because the removed vertices all have increased
penalty values, they are unlikely to be added
back into the current clique in the subsequent iterative improvement
phase. This is equivalent to restarting the search from $v$.
However, as a 
penalty delay of one corresponds to a behaviour in which
penalties are effectively not used at all 
(since an increase of any vertex penalty is immediately undone),
keeping even a single vertex of the current clique $C$
carries a high likelihood of reconstructing $C$ in the subsequent
iterative improvement phase. Therefore, to achieve a diversification
of the search, when the penalty delay is one, $C$ is 
perturbed by adding a vertex $v$ that is
chosen uniformly at random from the given graph $G$
and removing all vertices from $C$ that are not connected
to $v$.

As stated above, the penalty values are used in the selection
of a vertex from a given neighbour set $S$.
More precisely, the \emph{selectMinPenalty(S)} 
selects a vertex from $S$ 
by choosing uniformly at random
from the set of vertices in $S$ with minimal
penalty values. After a vertex has been 
selected from $S$, it becomes unavailable for 
subsequent selections until penalties have been updated
and perturbation has been performed. This prevents 
the plateau search phase from repeatedly visiting
the same clique. Also, as a safeguard to prevent penalty values 
%hh-final: added 'from':
from becoming too large, vertices with a penalty value greater than 10 are never selected.

\begin{figure}[tb]
{\footnotesize
\begin{tabbing}
24 \= 24 \= 24 \= 24 \= 24 \=     \kill
{\bf procedure} {\em \dls}($G$, \emph{tcs}, \emph{pd}, \emph{maxSteps})                        \\
\> {\bf input:} graph $G=(V,E)$; integers \emph{tcs} (target clique size),
		\emph{pd} (penalty delay), \emph{maxSteps}\\
\> {\bf output:} clique in $G$ of size at least \emph{tcs}
		{\bf or} `failed'\\
{\bf begin}                                                                        \\
%\> numSlc := 0;\\
%hh5: corrected:
\> \emph{numSteps} := 0;\\
%\>  $C$ := \emph{random($V$)};                           \\
%hh5: corrected:
\>  $C$ := $\{$\emph{random$(V)$}$\}$;                           \\
\>  \emph{initPenalties}; \\
\>  {\bf while} \emph{numSteps} $<$ \emph{maxSteps} {\bf do}                            \\
\>\>   $(C,v)$ := \emph{expand$(G,C)$}; \\
\>\> {\bf if} $|C| = $ \emph{tcs} {\bf then return}($C$); {\bf end if} \\
\>\>	 $C'$ := $C$; \\
\>\>   $(C,v)$ := \emph{plateauSearch$(G,C,C')$}; \\
\>\>   {\bf while} $N_I(C) \neq \emptyset$ {\bf do}                                    \\
\>\>\>   $(C,v)$ := \emph{expand$(G,C)$}; \\
\>\>\> {\bf if} $|C| = $ \emph{tcs} {\bf then return}($C$); {\bf end if} \\
\>\>\>   $(C,v)$ := \emph{plateauSearch$(G,C,C')$}; \\
\>\> {\bf end while}\\
\>\>  \emph{updatePenalties}(\emph{pd}); \\
\>\> {\bf if} $pd > 1$ {\bf then} \\
\>\>\>  $C$ := $\{v\}$;                                                          \\
\>\> {\bf else} \\
\>\>\>  $v$ := \emph{random$(V)$};                              \\
\>\>\>  $C$ := $C \cup \{v\}$; \\
\>\>\>	remove all vertices from $C$ that are not connected to $v$ in $G$; \\
\>\> {\bf end if} \\
\>  {\bf end while}                                                              \\
\> {\bf return}(`failed');\\
{\bf end}                                                                          \\  
\end{tabbing}
}
\vskip -0.2in
\caption{Outline of the \dls{} algorithm;
	for details, see text.}
\label{fig:dls}
\vskip -0.1in
\end{figure}

\begin{figure}[htb]
{\footnotesize
\begin{tabbing}
24 \= 24 \= 24 \= 24 \= 24 \=     \kill
{\bf procedure} {\em expand}($G,C$)                        \\
\> {\bf input:} graph $G=(V,E)$; vertex set $C \subseteq V$ (clique)\\
\> {\bf output:} vertex set $C \subseteq V$ (expanded clique);
		vertex $v$ (most recently added vertex)\\
{\bf begin}                                                                        \\

\>   {\bf while} $N_I(C) \neq \emptyset$ {\bf do}                                  \\
\>\>   $v$ := \emph{selectMinPenalty$(N_I(C))$};                                   \\
\>\>   $C := C \cup \{ v \}$;                                                \\
\>\>   \emph{numSteps} := \emph{numSteps} + 1;                                   \\
\> {\bf end while}; 	\\
\> {\bf return}($(C,v)$);\\
{\bf end}                                                                          \\  
\end{tabbing}
\begin{tabbing}
24 \= 24 \= 24 \= 24 \= 24 \=     \kill
{\bf procedure} {\em plateauSearch}($G,C,C'$)                        \\
\> {\bf input:} graph $G=(V,E)$; 
	vertex sets $C \subseteq V$ (clique),
%hh-final: changed 'memorised' -> 'recorded' (for consistency with text)
			$C' \subseteq C$ (recorded clique)\\
\> {\bf output:} vertex set $C \subseteq V$ (modified clique);
		vertex $v$ (most recently added vertex)\\
{\bf begin}                                                                        \\

\>   {\bf while} $N_I(C) = \emptyset$ 
				{\bf and} $N_L(C) \neq \emptyset$ 
				{\bf and} $C \cap C' \neq \emptyset$ {\bf do} \\
\>\>   $v$ := \emph{selectMinPenalty}$(N_L(C))$;                                   \\
%\>\>   $R := \{ v' \in C \mid (v,v') \notin E\}$; \\
\>\>   $C := C \cup \{ v \}$;                                                \\
\>\>   remove the vertex from $C$ that is not connected to $v$ in $G$; \\
\>\>   \emph{numSteps} := \emph{numSteps} + 1;                                 \\
\> {\bf end while}; 	\\
\> {\bf return}($(C,v)$);\\
{\bf end}                                                                          \\  
\end{tabbing}
}
\vskip -0.2in
\caption{Subsidiary search procedures of \dls{};
  for details, see text.}
\label{fig:procs}
\vskip -0.1in
\end{figure}

% [efficient implementation]
In order to implement \dls{} efficiently, all sets are maintained 
%hh-final: slightly reworded:
using two array data structures.
The first of these, the vertex list array, contains the vertices that are currently in the set; the second one, the vertex index array, is indexed by vertex number and contains the index of the vertex in the vertex list array (or $-1$, if the vertex is not in the set). All additions to the set are performed by adding to the end of the vertex list array and updating the vertex index array. Deletions from the set are performed by 
%moving the last entry in the vertex list over the entry in the vertex list of the vertex to be %deleted 
%hh5: reworded (for clarity):
overwriting the vertex list entry of the vertex to be deleted with
the last entry in vertex list
and then updating the vertex index array. 
Furthermore, as vertices can only be swapped once into the current clique during the plateau search phase, the intersection between the current clique and the recorded clique can be simply maintained by recording the size of the current clique at the start of the plateau search and decrementing this by one every time a vertex is swapped into the current clique. 
%hh-final: slightly reworded:
Finally, all array elements are accessed using pointers rather than 
via direct indexing of the array. \footnote{Several of these techniques are based on implementation details
of Henry Kautz's highly efficient WalkSAT code, see \url{http://www.cs.washington.edu/homes/kautz/walksat}.}

%hh2: modified (based on wp's comment):
Finally, it may be noted that in order to keep the time-complexity of the individual search steps
minimal, the selection from the improving and level neighbour sets
does not attempt to maximise the size of the set after the respective search step, but rather
chooses a vertex with minimal penalty uniformly at random; this is in keeping with 
the common intuition that, in the context of SLS algorithms, it is often preferable
to perform many relatively simple, but efficiently computable search steps rather than
fewer complex search steps.


\section{Empirical Performance Results}
\label{performance}

%hh2: slightly modified the following:
In order to evaluate the performance and behaviour of \dls{}, we 
performed extensive computational experiments on all MAX-CLIQUE 
instances from the Second DIMACS Implementation Challenge (1992--1993)\footnote {http://dimacs.rutgers.edu/Challenges/}, which have also been 
used extensively for benchmarking purposes in the recent literature on MAX-CLIQUE
algorithms. The 80 DIMACS MAX-CLIQUE instances were generated from problems in coding theory, fault diagnosis problems, Keller's conjecture on tilings using hypercubes
and the Steiner triple problem, in addition to randomly generated graphs and graphs where the maximum clique has been `hidden' by incorporating low-degree vertices. These 
%hh5: added 'instances'
problem instances range in size from less than $50$ vertices and $1\,000$ edges to greater than $3\,300$ vertices and $5\,000\,000$ edges.

%hh5: minor reformulation:
All experiments for this study were performed on
a dedicated 2.2 GHz Pentium IV machine with 512KB L2 cache and 512MB RAM, running Redhat Linux 3.2.2-5 and using the g++ C++ compiler with the `-O2' option. 
To execute the DIMACS Machine Benchmark\footnote{{\em dmclique}, ftp://dimacs.rutgers.edu in directory /pub/dsj/clique}, this machine required 0.72 CPU seconds for r300.5, 4.47 CPU seconds for r400.5 and 17.44 CPU seconds for r500.5.
In the following, unless explicitly stated otherwise, all CPU times refer to our
reference machine.

In the following sections, we first present results from a series of experiments that were aimed 
at providing a detailed assessment of the performance of \dls{}.
% section \ref{sub:results}
Then, we report additional experimental results that facilitate a more direct
comparison between \dls{} and other state-of-the-art MAX-CLIQUE algorithms. 
% These results are presented in section \ref{sub:comp}. 

\subsection{\dls{} Performance}
\label{sub:results}

To evaluate the performance of \dls{} on the DIMACS benchmark instances, 
we performed 100 independent runs of it for each instance, 
using target clique sizes ($tcs$) corresponding to the respective 
provably optimal clique sizes or, in cases where such provably optimal solutions
are unknown, largest known clique sizes.
In order to assess the peak performance of \dls{}, we conducted each such experiment
for multiple values of the penalty delay parameter, $pd$, and report
the best performance obtained.
The behaviour of \dls{} for suboptimal $pd$ values and the method used to identify the optimal $pd$ value are discussed in Section~\ref{s:weighting}.
The only remaining parameter of \dls{}, $maxSteps$, was set to $100\,000\,000$, in order
to maximise the probability of reaching the target clique size in every run.

\hide{
	\begin{itemize}
	\item[(a)] mention ranges of coefficient of variation (= stddev/mean) for clique and selections
		(and notable exceptions) in caption or text;
%hh3: now done for Table 2, DAGS
	\item[(h)] consider adding columns with number of vertices and avg edge density of graphs;
%hh3: information provided in table 3 / appendix
	\end{itemize}
}

The results from these experiments are displayed in Table~\ref{tab:dls-performance}. For each benchmark instance we show the \dls{} performance results (averaged over 100 independent runs) 
for the complete set of 80 DIMACS benchmark instances. Note that \dls{} finds optimal (or best known) solutions with a success rate of 100\% 
%hh5: added (for clarity):
over all 100 runs per instance 
for 77 of the 80 instances; the only cases where the target clique size
was not reached consistently within the alotted 
%hh-final: slightly reworded:
maximum number of search steps
($maxSteps$) are: 
\begin{itemize}
\item C2000.9, where 93 of 100 runs were successful giving a maximum clique size (average clique size, minimum clique size) of 78 (77.93, 77); 
%hh-final: minor rewording (for clarity) -- CHECK FOR ACCURACY!:
\item MANN\_a81, where 96 of 100 runs obtained cliques of size
1098, while the remaining runs produced cliques of size 1097; and 
\item MANN\_a45, where all runs achieved a maximum clique size of 344.
\end{itemize}
For these three cases, the reported CPU time statistics are over successful runs only and are shown in parentheses in Table~\ref{tab:dls-performance}. Furthermore, the expected time required by \dls{} to reach the target clique size is less than 1 CPU second for 67 of the 80 instances, and an
\setlength{\tabcolsep}{1.5mm}
\begin{table}[!p]
{\scriptsize
\begin{center}
\begin{tabular}{|r|r|r|r|r|r||r|r|r|r|r|r|}
\hline
\multicolumn{1}{|c|}{Instance}&\multicolumn{1}{|c|}{BR}&
\multicolumn{1}{|c|}{\emph{pd}}&\multicolumn{1}{|c|}{CPU(s)}&
\multicolumn{1}{|c|}{Steps}&\multicolumn{1}{|c||}{Sols.}&
\multicolumn{1}{|c|}{Instance}&\multicolumn{1}{|c|}{BR}&
\multicolumn{1}{|c|}{\emph{pd}}&\multicolumn{1}{|c|}{CPU(s)}&
\multicolumn{1}{|c|}{Steps}&\multicolumn{1}{|c|}{Sols.}\\
\hline \hline
brock200\_1&21&2&0.0182&14091&2&sanr200\_0.9&42&2&0.0127&15739&18\\
brock200\_2&12*&2&0.0242&11875&1&sanr400\_0.5&13&2&0.0393&9918&4\\
brock200\_3&15&2&0.0367&21802&1&sanr400\_0.7&21&2&0.023&8475&61\\
brock200\_4&17*&2&0.0468&30508&1&C1000.9&68&1&4.44&1417440&70\\
brock400\_1&27&15&2.2299&955520&1&C125.9&34*&1&0.0001&158&94\\
brock400\_2&29*&15&0.4774&205440&1&C2000.5&16&1&0.9697&50052&93\\
%hh-final: here and in the following, I put the number of opt solutions in parentheses
%		for cases where the target solution quality was not reached:
brock400\_3&31&15&0.1758&74758&1&C2000.9&78&1&(193.224)&(29992770)&(91)\\
brock400\_4&33*&15&0.0673&28936&1&C250.9&44*&1&0.0009&845&85\\
brock800\_1&23&45&56.4971&10691276&1&C4000.5&18&1&181.2339&5505536&93\\
brock800\_2&24&45&15.7335&3044775&1&C500.9&57&1&0.1272&72828&3\\
brock800\_3&25&45&21.9197&4264921&1&c-fat200-1&12&1&0.0002&24&14\\
brock800\_4&26&45&8.8807&1731725&1&c-fat200-2&24&1&0.001&291&1\\
DSJC1000\_5&15*&2&0.799&91696&25&c-fat200-5&58&1&0.0002&118&3\\
DSJC500\_5&13*&2&0.0138&2913&42&c-fat500-1&14&1&0.0004&45&19\\
hamming10-2&512&5&0.0008&1129&2&c-fat500-10&126&1&0.0015&276&3\\
hamming10-4&40&5&0.0089&1903&100&c-fat500-2&26&1&0.0004&49&18\\
hamming6-2&32&5&$< \epsilon$&43&2&c-fat500-5&64&1&0.002&301&3\\
hamming6-4&4&5&$< \epsilon$&3&83&gen200\_p0.9\_44&44*&1&0.001&1077&4\\
hamming8-2&128&5&0.0003&244&100&gen200\_p0.9\_55&55*&1&0.0003&369&4\\
hamming8-4&16*&5&$< \epsilon$&31&92&gen400\_p0.9\_55&55&1&0.0268&18455&1\\
johnson16-2-4&8&5&$< \epsilon$&7&100&gen400\_p0.9\_65&65&1&0.001&716&1\\
johnson32-2-4&16&5&$< \epsilon$&15&100&gen400\_p0.9\_75&75&1&0.0005&402&1\\
johnson8-2-4&4&5&$< \epsilon$&3&66&keller4&11*&1&$< \epsilon$&31&98\\
johnson8-4-4&14&5&$< \epsilon$&21&29&keller5&27&1&0.0201&4067&100\\
MANN\_a27&126*&3&0.0476&41976&100&keller6&59&1&170.4829&11984412&100\\
MANN\_a45&345*&3&(51.9602)&(16956750)&(100)&p\_hat1000-1&10&1&0.0034&230&82\\
MANN\_a81&1099&3&(264.0094)&(27840958)&(96)&p\_hat1000-2&46&1&0.0024&415&87\\
MANN\_a9&16&3&$<\epsilon$&21&99&p\_hat1000-3&68&1&0.0062&1579&23\\
san1000&15&85&8.3636&521086&1&p\_hat1500-1&12*&1&2.7064&126872&1\\
san200\_0.7\_1&30&2&0.0029&1727&1&p\_hat1500-2&65&1&0.0061&730&90\\
san200\_0.7\_2&18&2&0.0684&33661&2&p\_hat1500-3&94&1&0.0103&1828&98\\
san200\_0.9\_1&70&2&0.0003&415&1&p\_hat300-1&8*&1&0.0007&133&13\\
san200\_0.9\_2&60&2&0.0002&347&1&p\_hat300-2&25*&1&0.0002&87&42\\
san200\_0.9\_3&44&2&0.0015&1564&1&p\_hat300-3&36*&1&0.0007&476&10\\
san400\_0.5\_1&13&2&0.1641&26235&1&p\_hat500-1&9&1&0.001&114&48\\
san400\_0.7\_1&40&2&0.1088&29635&1&p\_hat500-2&36&1&0.0005&200&14\\
san400\_0.7\_2&30&2&0.2111&57358&1&p\_hat500-3&50&1&0.0023&1075&36\\
san400\_0.7\_3&22&2&0.4249&113905&1&p\_hat700-1&11*&1&0.0194&1767&2\\
san400\_0.9\_1&100&2&0.0029&1820&1&p\_hat700-2&44*&1&0.001&251&72\\
sanr200\_0.7&18&2&0.002&1342&13&p\_hat700-3&62&1&0.0015&525&85\\
\hline
\end{tabular}
\end{center}
}
\vskip -0.2in
\caption{\dls{} performance results, averaged over 100 independent runs, for the complete set of DIMACS benchmark instances. 
%The best result found by an algorithm (* if optimality proven) for each instance is %shown in the BR column;
The maximum known clique size for each instance is shown in the BR column
(marked with an asterisk where proven to be optimal);
\emph{pd} is the 
%optimal
%hh5: since we don't know it is truly optimal:
optimised 
\dls{} penalty delay for each instance; CPU(s) is the 
%processor time,
%hh5: changed to:
run-time in CPU seconds, 
averaged over all successful runs, for each instance. Average CPU times less than 0.0001 
%hh5: added:
seconds
are shown as $<\epsilon$; `Steps' is the number of vertices added to the clique, averaged over all successful runs,  for each instance; `Sols.' is the total number of distinct maximum sized cliques found for each instance. All runs achieved the best known cliques size shown with the exception of: C2000.9, where 93 of 100 runs were successful giving a maximum clique size (average clique size, minimum clique size) of 78(77.93, 77); MANN\_a81, where 96 of 100 runs obtained 1098 giving 1098(1097.96, 1097); 
and MANN\_a45, where all runs achieved a maximum clique size of 344.}
\label{tab:dls-performance}
\vskip -0.1in
\end{table}
\setlength{\tabcolsep}{0.5mm}
\clearpage
\noindent
expected run-time of more than 10 CPU seconds is only required for 
8 of the 13 remaining instances, all of which have at least 800 vertices.
Finally, the variation coefficients (stddev/mean) of the run-time distributions
(measured in search steps,
in order to overcome inaccuracies inherent to extremely small CPU times) 
for the instances on which 100\% success rate
was obtained were found to reach average and maximum values of 
0.86  and 1.59, respectively.

It may be interesting to note that the time-complexity of search steps in \dls{} 
is generally very low. As an indicative example, {\tt brock800\_1} with
800 vertices, $207\,505$ edges and a maximum clique size of 23 vertices, \dls{} performs,
on average, $189\,235$ search steps (\emph{i.e.}, additions to the current clique) per CPU second.
Generally, the time-complexity of \dls{} steps increases with the size of the improving ($N_I$) and level ($N_L$) neighbour sets as well as, to a lesser degree, with the maximum clique size. 
This relationship can be seen from Table \ref{tab:dls-cnnnn} which shows, for the (randomly 
generated) DIMACS C$\ast$.9 and brock$\ast$\_1 instances, how the performance of \dls{} in terms of search steps per CPU second
decreases as the number of vertices (and hence the size of $N_I$, $N_L$) increases.

%hh3: doesn't fit as nicely anymore, since we now have to mention the brock instances:
\hide{
(these instances have an edge density, 
\ie{}, average number of edges per vertex, 
of $0.9$). 
}%
\setlength{\tabcolsep}{1.5mm}
\begin{table}[htb]
{\scriptsize
\begin{center}
\begin{tabular}{|r|r|r|r|r|r|}
\hline
Instance & Vertices & Edges & BR & \dls{} \emph{pd} & Steps / Second \\
\hline
\hline
C125.9&125&6963 & 34& 1 & 1587399 \\
C250.9&250&27984 & 44& 1 & 939966 \\
C500.9&500& 112332& 57& 1 & 572553 \\
C1000.9&1000&450079 & 68& 1 & 319243  \\
C2000.9&2000& 1799532& 78& 1 & 155223 \\
\hline
brock200\_1&200& 14834& 21& 2 & 774231 \\
brock400\_1&400& 59723& 27& 15 & 428504 \\
brock800\_1&800& 207505& 23& 45 & 189236 \\
\hline
\end{tabular}
\end{center}
}
\vskip -0.2in
\caption{Average number of \dls{} search steps per CPU second
(on our reference machine) over 100 runs for the DIMACS C$\ast$.9 and brock$\ast$\_1 instances. 
The `BR' and `DLS-MC $pd$' figures from Table~\ref{tab:dls-performance} are 
%replicated
%hh5: changed
also shown,
as these factors have a direct impact on the performance of \dls{}. That is, as BR increases,
the greater the overhead in maintaining the sets within \dls{};
%hh-final: minor rewording:
furthermore, larger \emph{pd} values cause higher overhead for maintaing penalties,
%hh5: added:
because more vertices tend to be penalised.
The C$\ast$.9 instances are randomly generated with an edge probability of 0.9, while the brock$\ast$\_1 instances are constructed so as to `hide' the maximum clique
and have considerably lower densities (\ie{}, average number of edges per vertex).
%hh3: slightly modified:
The scaling of the average number of search steps per CPU second performed by \dls{} 
on the C$\ast$.9 instances only, running on our reference machine,
can be approximated as $9 \cdot 10^7 \cdot n^{-0.8266}$,
where $n$ is the number of vertices in the given graph
(this approximation achieves an $R^2$ value of 0.9941).
} 
\label{tab:dls-cnnnn}
\vskip -0.1in
\end{table}
\setlength{\tabcolsep}{0.5mm}
A more detailed analysis of \dls{}'s performance in terms of implementation-independent measures of run-time, such as 
%hh-final: added:
search steps or 
iteration counts, is beyond the scope of this work, but could yield useful insights in the future.

\subsection{Comparative Results}

%hh3: minor changes throughout this section:

\label{sub:comp}
% [motivation, protocol]
The results reported in the previous section demonstrate clearly that \dls{} achieves
excellent performance on the standard DIMACS benchmark instances. However, a comparative analysis of these results, as compared to 
%hh5: added for clarity:
the results found in the literature on 
other state-of-the-art MAX-CLIQUE algorithms, is not a straight-forward task because of differences in:

\begin{itemize}
\item {\bf Computing Hardware:} To date, computing hardware has basically been documented in terms of CPU speed which only allows a very basic means of comparison (\ie{}, by scaling based on the computer CPU speed which, for example, takes no account of other features, such as memory caching, memory size, hardware architecture, \etc{}). Unfortunately, for some algorithms, this was the only realistic option available to us
for this comparison. 

%hh3: I've changed the following quite a bit:
\item {\bf Result Reporting Methodology:}
Most empirical results on the performance of MAX-CLIQUE algorithms found in the
literature are in the form of statistics on the clique size obtained after a fixed
run-time. To conduct performance comparisons on such data, care must be taken
to avoid 
%inclusive situatons 
%hh5: corrected (is this what we meant?)
inconclusive situations
in which an algorithm $A$ achieves larger clique sizes 
than another algorithm $B$, but at the cost of higher run-times.
%hh5: removed (since the following is really the justification for what was argued before):
%Also, 
It is important to realise that the relative performance of $A$ and $B$ can vary substantially with run-time; while $A$ may reach higher clique sizes than $B$
for relatively short run-times, the opposite could be the case for longer run-times.
Finally, seemingly small differences in clique size may in fact represent
major differences in performance, since (as in many hard optimisation problems)
finding slightly sub-optimal cliques is typically substantially easier than
finding maximal cliques.
\hide{
The use of the result reporting format `maximum clique size (average clique size, minimum clique size)' after a fixed number of steps also presents difficulties when comparing results. 
For example, how can a conclusion be drawn when algorithm A has a higher average clique size than algorithm B but also has a higher average CPU time? In addition, this reporting format tends to make a meaningful comparison of results difficult as, for some instances, finding a clique whose size is very close to maximal is can be substantially easier than finding a maximum clique.
}%
For example, for C2000.9, the average time needed
to find a clique of size 77 (with 100\% success rate) is 6.419 CPU seconds, whereas reaching the maximum clique size of 78 (with 93\% success rate) requires on average (over successful runs only) of 193.224 CPU seconds. 

%hh3: I've cut out the comments about RTD-based analysis, since we talk about
%	this later and don't really need it here.

\item {\bf Termination Criteria:} Some MAX-CLIQUE algorithms (such as DAGS) do not 
terminate upon reaching a given target clique size, but will instead 
run for a given number of search steps or fixed amount of CPU time, 
even if an optimal clique is encountered early in the search. 
It would obviously be highly unfair to directly compare published results for such algorithms with those of \dls{}, which terminates 
%immediately 
%hh5: changed:
as soon as
it finds the user supplied target clique size.
\end{itemize}

\noindent
Therefore, to confirm that \dls{} represents a significant improvement over previous state-of-the-art MAX-CLIQUE algorithms, we conducted further experiments and analyses designed to yield performance results for \dls{} that can be more directly compared with the results of other MAX-CLIQUE algorithms. 
In particular, we compared \dls{} with the following MAX-CLIQUE algorithms:
DAGS~\cite{GroLocDel04}, GRASP~\cite{resetal98} (using the results contained in ~\citeR{GroLocDel04}), k-opt~\cite{KatEtAl04}, RLS~\cite{BatPro01}, GENE~\cite{mar02}, ITER~\cite{mar02} and QUALEX-MS~\cite{Busygin02}.
To rank the performance of MAX-CLIQUE algorithms and to determine
the dominant algorithm for each of our benchmark instances, we used a set of criteria that are based, primarily, on the quality of the solution and then, when this is deemed equivalent, on the 
%processor 
%hh5: I've changed all remaining occurrences of 'processor time' to 'CPU time' (for consistency)
CPU time 
requirements of the algorithms.
These criteria are shown, in order of application, in Table~\ref{tab:alg-rank-crit}.

\begin{table}[htb]
{\scriptsize
\begin{center}
\begin{tabular}{|ll|}
\hline
&\\
1. & If an algorithm is the only algorithm to find the largest known maximum clique for an instance then it is \\
&ranked as the dominant algorithm for that instance. \\
&\\
2. & If more than one algorithm achieves a 100\% success rate for an instance then the algorithm with the lowest \\ &average (scaled) CPU time becomes the dominant algorithm for that instance. \\
&\\
3. & If a single algorithm achieves a 100\% success rate for an instance then that algorithm becomes the dominant\\ &algorithm for that instance. \\
&\\
4. & If no algorithm achieves a 100\% success rate for an instance, then the algorithm that achieves the largest \\
&size clique, has the highest average clique size and the lowest average CPU time becomes the \\
&dominant algorithm for that instance. \\
&\\
5. & If, for any instance, no algorithm meets any of the four criteria listed above, then no conclusion can be \\
&drawn about which is the dominant algorithm for that instance. \\
&\\
\hline
\end{tabular}
\end{center}
}
\vskip -0.2in
\caption{The criteria used for ranking MAX-CLIQUE algorithms.} 
\label{tab:alg-rank-crit}
\vskip -0.1in
\end{table}

%hh4: major rewriting from here:

\setlength{\tabcolsep}{1.5mm}
\begin{table}[!b]
{\scriptsize
\begin{center}
\begin{tabular}{|r|r|r|r|r|r|r|}
\hline
&\multicolumn{2}{|c|}{\dls{}} &\multicolumn{2}{|c|}{DAGS{}}&\multicolumn{2}{|c|}{GRASP} \\
\hline
\multicolumn{1}{|c|}{Instance}&\multicolumn{1}{|c|}{Clique size}&
\multicolumn{1}{|c|}{CPU(s)}&\multicolumn{1}{|c|}{Clique size}&
\multicolumn{1}{|c|}{SCPU(s)}&\multicolumn{1}{|c|}{Clique size}&
\multicolumn{1}{|c|}{SCPU(s)}\\
\hline \hline
brock200\_1&21&0.0182&21&0.256&21&4.992\\
brock200\_2&12&0.0242&12&0.064&12&1.408\\
brock200\_3&15&0.0367&15&0.064&14&42.56\\
brock200\_4&17&0.0468&17(16.8,16)&0.192&17&3.328\\
brock400\_1&27&2.2299&27(25.35,24)&1.792&25&14.976\\
brock400\_2&29&0.4774&29(28.1,24)&1.792&25&15.232\\
brock400\_3&31&0.1758&31(30.7,25)&1.792&31(26.2,25)&14.848\\
brock400\_4&33&0.0673&33&1.792&25&15.232\\
brock800\_1&23&56.4971&23(20.95,20),&10.624&21&32\\
brock800\_2&24&15.7335&24(20.8,20)&10.752&21&32.96\\
brock800\_3&25&21.9197&25(22.2,21)&10.88&22(21.85,21)&34.112\\
brock800\_4&26&8.8807&26(22.6,20)&10.816&21&33.152\\
\hline
C1000.9&68&4.44&68(65.95,65)&94.848&67(66.1,65)&154.368\\
C2000.9&78(77.93,77)&193.224&76(75.4,74)&1167.36&75(74.3,73)&466.368\\
C4000.5&18&181.2339&18(17.5,17)&2066.56&18(17.75,17)&466.944\\
C500.9&57&0.1272&56(55.85,55)&8.64&56&80.896\\
\hline
gen200\_p0.9\_44&44&0.001&44(41.15,40)&0.576&44(41.95,41)&11.776\\
gen400\_p0.9\_55&55&0.0268&53(51.8,51)&4.608&53(52.25,52)&35.264\\
gen400\_p0.9\_65&65&0.001&65(55.4,51)&4.672&65(64.3,63)&34.56\\
gen400\_p0.9\_75&75&0.0005&75(55.2,52)&4.992&74(72.3,69)&36.16\\
\hline
keller6&59&170.4829&57(56.4,56)&7888.64&55(53.5,53)&1073.792\\
\hline
MANN\_a45&344&51.9602&344(343.95)&1229.632&336(334.5,334)&301.888\\
\hline
p\_hat1000-3&68&0.0062&68(67.85,67)&71.872&68&237.568\\
p\_hat1500-1&12&2.7064&12(11.75,11)&19.904&11&23.424\\
\hline
san200\_0.7\_2&18&0.0684&18(17.9,17)&0.192&18(16.55,15)&3.264\\
san400\_0.7\_3&22&0.4249&22(21.7,19)&1.28&21(18.8,17)&9.856\\
sanr200\_0.9&42&0.0127&42(41.85,41)&0.576&42&12.608\\
\hline
\end{tabular}
\end{center}
}
\vskip -0.2in
%hh-final: slightly reworded:
\caption{Performance comparison of \dls{}, DAGS and GRASP for selected DIMACS instances. The SCPU columns contain the scaled DAGS and GRASP average run-times in CPU seconds;
DAGS and GRASP results are based on 20 runs per instance, and
\dls{} results are based
on 100 runs per instance. 
%hh-final: minor rewording:
In cases where the best known result was not found in all runs,
clique size entries are in the format `maximum clique size (average clique size, minimum clique size)'. 
\dls{} is the dominant algorithm for all instances in this table.} 
\label{tab:dls-dags-1}
\vskip -0.1in
\end{table}
\setlength{\tabcolsep}{0.5mm}
\clearpage
Table~\ref{tab:dls-dags-1} contrasts performance results for DAGS and GRASP
from the literature \cite{GroLocDel04} with the respective performance results
for \dls{}. Since the DAGS and GRASP runs had been performed on a 1.4 GHz Pentium IV CPU, while \dls{} ran on our 2.2 GHz 
%hh5: added (for clarity):
Pentium IV
reference machine, we scaled their CPU times
by a factor or 0.64. (Note that this is based on the assumption
of a linear scaling of run-time with CPU clock speed; in reality,
the speedup is typically significantly smaller.)
Using our ranking criteria, this data shows that \dls{} dominates 
both DAGS and GRASP for all the benchmark instances listed in Table~\ref{tab:dls-dags-1}. 
To confirm this ranking, we modified DAGS so 
it terminated as soon a given target clique size was reached 
(this is the termination condition used in \dls{}) and performed a direct comparison
with \dls{} on all 80 DIMACS instances,
running both algorithms on our reference machine.
As can be seen from the results of this experiment, shown in 
Table~\ref{tab:dls-dags-2}, 
\dls{} dominates DAGS on all but one instance (the exception being 
san1000).
\setlength{\tabcolsep}{1.5mm}
\begin{table}[!b]
{\scriptsize
\begin{center}
\begin{tabular}{|r|r|r|r|r||r|r|r|r|r|}
\hline
&\multicolumn{2}{|c|}{\dls{}}&\multicolumn{2}{|c||}{DAGS}&
&\multicolumn{2}{|c|}{\dls{}}&\multicolumn{2}{|c|}{DAGS}\\
\hline
\multicolumn{1}{|c|}{Instance}&\multicolumn{1}{|c|}{Success}&
\multicolumn{1}{|c|}{CPU(s)}&\multicolumn{1}{|c|}{Success}&
\multicolumn{1}{|c||}{CPU(s)}&\multicolumn{1}{|c|}{Instance}&
\multicolumn{1}{|c|}{Success}&\multicolumn{1}{|c|}{CPU(s)}&
\multicolumn{1}{|c|}{Success}&\multicolumn{1}{|c|}{CPU(s)}\\
\hline \hline
brock200\_1&100&0.0182&93&0.1987&johnson32-2-4&100&$<\epsilon$&100&0.0042\\
brock200\_2&100&0.0242&98&0.1252&johnson8-2-4&100&$<\epsilon$&100&$<\epsilon$\\
brock200\_3&100&0.0367&100&0.1615&johnson8-4-4&100&$<\epsilon$&100&0.0001\\
brock200\_4&100&0.0468&82&0.2534&keller4&100&$<\epsilon$&100&0.0009\\
brock400\_1&100&2.2299&35&3.1418&keller5&100&0.0201&100&0.079\\
brock400\_2&100&0.4774&75&2.3596&keller6&100&170.4829&$-$&$-$\\
brock400\_3&100&0.1758&92&2.2429&MANN\_a27&100&0.0476&100&0.1886\\
brock400\_4&100&0.0673&99&1.653&MANN\_a45&100&51.9602&94&8.194\\
brock800\_1&100&56.4971&9&20.0102&MANN\_a81&96&264.0094&$-$&$-$\\
brock800\_2&100&15.7335&20&18.747&MANN\_a9&100&$<\epsilon$&100&0.0003\\
brock800\_3&100&21.9197&19&19.1276&p\_hat1000-1&100&0.0034&100&0.0353\\
brock800\_4&100&8.8807&45&16.9227&p\_hat1000-2&100&0.0024&100&0.0984\\
DSJC1000\_5&100&0.799&80&7.238&p\_hat1000-3&100&0.0062&81&37.2\\
DSJC500\_5&100&0.0138&100&0.1139&p\_hat1500-1&100&2.7064&69&15.609\\
C1000.9&100&4.44&5&2.87&p\_hat1500-2&100&0.0061&100&0.4025\\
C125.9&100&0.0001&100&0.0024&p\_hat1500-3&100&0.0103&100&6.3255\\
C2000.9&93&193.224&5&2.870608&p\_hat300-1&100&0.0007&100&0.0078\\
C2000.5&100&0.9697&100&17.9247&p\_hat300-2&100&0.0002&100&0.0033\\
C250.9&100&0.0009&99&0.1725&p\_hat300-3&100&0.0007&100&0.0609\\
C4000.5&100&181.2339&$-$&$-$&p\_hat500-1&100&0.001&100&0.0099\\
C500.9&100&0.1272&4&16.2064&p\_hat500-2&100&0.0005&100&0.0215\\
c-fat200-1&100&0.0002&100&0.0002&p\_hat500-3&100&0.0023&100&0.4236\\
c-fat200-2&100&0.001&100&0.0004&p\_hat700-1&100&0.0194&100&0.1217\\
c-fat200-5&100&0.0002&100&0.0012&p\_hat700-2&100&0.001&100&0.0415\\
c-fat500-1&100&0.0004&100&0.0005&p\_hat700-3&100&0.0015&100&0.1086\\
c-fat500-10&100&0.0015&100&0.0067&san1000&100&8.3636&100&0.967\\
c-fat500-2&100&0.0004&100&0.0009&san200\_0.7\_1&100&0.0029&100&0.0029\\
c-fat500-5&100&0.002&100&0.0028&san200\_0.7\_2&100&0.0684&92&0.1001\\
gen200\_p0.9\_44&100&0.001&14&0.9978&san200\_0.9\_1&100&0.0003&100&0.0023\\
gen200\_p0.9\_55&100&0.0003&100&0.0267&san200\_0.9\_2&100&0.0002&100&0.0368\\
gen400\_p0.9\_55&100&0.0268&0&9.0372&san200\_0.9\_3&100&0.0015&100&0.0572\\
gen400\_p0.9\_65&100&0.001&27&7.1492&san400\_0.5\_1&100&0.1641&100&0.0336\\
gen400\_p0.9\_75&100&0.0005&14&8.6018&san400\_0.7\_1&100&0.1088&100&0.0089\\
hamming10-2&100&0.0008&100&0.1123&san400\_0.7\_2&100&0.2111&100&0.0402\\
hamming10-4&100&0.0089&100&3.8812&san400\_0.7\_3&100&0.4249&90&0.5333\\
hamming6-2&100&$<\epsilon$&100&0.0003&san400\_0.9\_1&100&0.0029&100&0.0322\\
hamming6-4&100&$<\epsilon$&100&$<\epsilon$&sanr200\_0.7&100&0.002&100&0.0239\\
hamming8-2&100&0.0003&100&0.0039&sanr200\_0.9&100&0.0127&83&0.3745\\
hamming8-4&100&$<\epsilon$&100&0.0006&sanr400\_0.5&100&0.0393&93&0.231\\
johnson16-2-4&100&$<\epsilon$&100&0.0003&sanr400\_0.7&100&0.023&100&0.1345\\
\hline
\end{tabular}
\end{center}
}
\vskip -0.2in
%hh-final: minor rewording:
\caption{Success rates and average CPU times for \dls{} and DAGS (based
on 100 runs per instance). For the 80 DIMACS instances, \dls{} had a superior success rate for 31 instances and, with exception of san1000, required less or the same CPU time than DAGS for all other instances. Entries of `$-$' signify that the runs were terminated because of excessive CPU time requirements. To obtain a meaningful comparison for \dls{} and DAGS, for MANN\_a45 and MANN\_a81, 344 and 1098 respectively were used as best known results in producing this table. For both \dls{} and DAGS, the average CPU time is over successful runs only. Using the ranking criteria of this study, DAGS is the dominant algorithm for the san1000 instance, while \dls{} is the dominant algorithm for all other instances.} 
\label{tab:dls-dags-2}
\vskip -0.1in
\end{table}
\setlength{\tabcolsep}{0.5mm}


%hh3: The following results don't add much, I therefore commented them (and
%	the respective table) out.
\hide{
For the second experiment, the maximum number of search steps ($maxSteps$) in \dls{} was reduced to a value for which the expected size of the maximum clique as determined over 100 runs of \dls{}
matched or closely exceeded the corresponding values reported for DAGS \cite{GroLocDel04}. This allows, given we know the relative speed of the computing hardware used for \dls{} and DAGS, a more direct comparison of the relative performance of \dls{} and DAGS. These results are presented in Table~\ref{tab:dls-dags-3} and confirm that, for the brock800 instances, \dls{} is superior to DAGS in performance.
}


Table~\ref{tab:dls-kopt-1} shows performance results for \dls{} as
compared to results for k-opt~\cite{KatEtAl04}, GENE~\cite{mar02}, ITER~\cite{mar02} 
and RLS~\cite{BatPro01} from the literature.
To roughly compensate for differences in CPU speed,
we scaled the CPU times for k-opt, GENE and ITER by a factor of 0.91 
(these had been obtained on a 2.0 GHz Pentium IV)
and those for RLS (measured on a 450 MHz Pentium II CPU) by 0.21.
Using the ranking criteria in Table~\ref{tab:alg-rank-crit}, RLS is the dominant algorithm for instances keller6 and MANN\_a45, k-opt is the dominant algorithm for MANN\_a81 and \dls{} is the dominant algorithm, with the exception of C2000.9, for the remainder of the DIMACS instances listed in Table~\ref{tab:dls-kopt-1}. 
To identify the dominant algorithm for C2000.9, a further experiment was performed,
running \dls{} with its $maxSteps$ parameter (which controls the maximum allowable run-time) reduced to the point where the average clique size for \dls{} just exceeded that reported for RLS. 
\hide{
The results obtained were success rate = 58\%, maximum clique size = 78, average clique size = 77.58, minimum clique size = 77, average CPU time = 84.9995 seconds
}%
In this experiment, \dls{} reached the optimum clique size of 
78 in 58 of 100 independent runs with an average and minimum clique size of
77.58 and 77, respectively and an average run-time of 85 CPU sec 
(taking into account all runs).
This establishes \dls{} as dominant over RLS and k-opt on instance C2000.9.

\setlength{\tabcolsep}{0.7mm}
\begin{table}[htb]
\vskip -0.3in
{\scriptsize
\begin{center}
\begin{tabular}{|r|r|r|r|r|r|r|r|r|}
\hline
&\multicolumn{2}{|c|}{\dls{}}&\multicolumn{2}{|c|}{k-opt}&
\multicolumn{2}{|c|}{RLS}&GENE&ITER\\
\hline
&&&&&&&\multicolumn{1}{|c|}{Avg.}&
\multicolumn{1}{|c|}{Avg.}\\
\multicolumn{1}{|c|}{Instance}&\multicolumn{1}{|c|}{Clique size}&
\multicolumn{1}{|c|}{CPU(s)}&\multicolumn{1}{|c|}{Clique size}&
\multicolumn{1}{|c|}{SCPU(s)}&\multicolumn{1}{|c|}{Clique size}&
\multicolumn{1}{|c|}{SCPU(s)}&\multicolumn{1}{|c|}{Clique size}&
\multicolumn{1}{|c|}{Clique size}\\
\hline \hline
brock200\_2&12&0.0242&11&0.02184&12&2.01705&10.5&10.5\\
brock200\_4&17&0.0468&16&0.01911&17&4.09311&15.4&15.5\\
brock400\_2&29&0.4774&25(24.6,24)&0.28028&29(26.063,25)&8.83911&22.5&23.2\\
brock400\_4&33&0.0673&25&0.18291&33(32.423,25)&22.81398&23.6&23.1\\
brock800\_2&24&15.7335&21(20.8,20)&2.16034&21&0.99519&19.3&19.1\\
brock800\_4&26&8.8807&21(20.5,20)&2.50796&21&1.40616 &18.9&19\\
\hline C1000.9&68&4.44&67&6.3063&68&8.7486
&61.6&61.6\\
C125.9&34&0.0001&34&0.00091&34&0.00084
&33.8&34\\
C2000.5&16&0.9697&16&13.01846&16&2.09496
&14.2&14.2\\
C2000.9&78(77.9,77)&193.224&77(75.1,74)&66.14608&78(77.575,77)&172.90518
&68.2&68.7\\
C250.9&44&0.0009&44&0.05642&44&0.00609
&42.8&43\\
C4000.5&18&181.2339&17&65.27885&18&458.44869
&15.4&15.6\\
C500.9&57&0.1272&57(56.1,56)&0.82264&57&0.65604
&52.2&52.7\\
\hline
DSJC1000\_5&15&0.799&15&5.77941&15&1.35513
&13.3&13.5\\
DSJC500\_5&13&0.0138&13&0.12103&13&0.04074
&12.2&12.1\\
\hline
gen200\_p0.9\_44&44&0.001&44&0.06643&44&0.00777
&39.7&39.5\\
gen200\_p0.9\_55&55&0.0003&55&0.00273&55&0.00336
&50.8&48.8\\
gen400\_p0.9\_55&55&0.0268&53(52.3,51)&0.56238&55&0.25284&49.7&49.1\\
gen400\_p0.9\_65&65&0.001&65&0.24934&65&0.0105
&53.7&51.2\\
gen400\_p0.9\_75&75&0.0005&75&0.16926&75&0.01071
&60.2&62.7\\
\hline
hamming10-4&40&0.0089&40&0.58422&40&0.01638
&37.7&38.8\\
hamming8-4&16&$<\epsilon$&16&0.00182&16&0.00063
&16&16\\
\hline
keller4&11&$<\epsilon$&11&0.00091&11&0.00042
&11&11\\
keller5&27&0.0201&27&0.07371&27&0.03591
&26&26.3\\
keller6&59&170.4829&57(55.5,55)&125.03218&59&39.86094&51.8&52.7\\
\hline
MANN\_a27&126&0.0476&126&0.03276&126&0.65436
&125.6&126\\
MANN\_a45&344&51.9602&344(343.6,343)&5.34716&345(343.6,343)&83.7417&342.4&343.1\\
MANN\_a81&1098(1097.96,1097)&264.0094&1099(1098.1,1098)&84.903&1098&594.4722
&1096.3&1097\\
\hline
p\_hat1500-1&12&2.7064&12&15.43997&12&6.35754
&10.8&10.4\\
p\_hat1500-2&65&0.0061&65&0.42224&65&0.03318
&63.8&63.9\\
p\_hat1500-3&94&0.0103&94&2.093&94&0.04032
&92.4&93\\
p\_hat300-1&8&0.0007&8&0.00637&8&0.00378
&8&8\\
p\_hat300-2&25&0.0002&25&0.00546&25&0.00126
&25&25\\
p\_hat300-3&36&0.0007&36&0.0273&36&0.00441
&34.6&35.1\\
p\_hat700-1&11&0.0194&11&0.57876&11&0.03906
&9.8&9.9\\
p\_hat700-2&44&0.001&44&0.04914&44&0.00588
&43.5&43.6\\
p\_hat700-3&62&0.0015&62&0.08008&62&0.00735
&60.4&61.8\\
\hline
\end{tabular}
\end{center}
}
\vskip -0.2in
\caption{Performance of \dls{}, k-opt, RLS, GENE and ITER for selected DIMACS instances. The SCPU columns contain the scaled average run-time in CPU seconds for k-opt and RLS;
\dls{} and RLS results are based on 100 runs per instance,
and the k-opt, GENE and ITER results are based on 10 runs per instance.
 Using the ranking criteria of this study, RLS is the dominant algorithm for instances MANN\_a45 and keller6, while \dls{} is the dominant algorithm for all other instances.} 
\label{tab:dls-kopt-1}
\vskip -0.2in
\end{table}
\setlength{\tabcolsep}{0.5mm}


Analagous experiments were performed to directly compare the performance
of \dls{} and k-opt on selected DIMACS benchmark instances;
the results, shown in Table~\ref{tab:dls-kopt-2}, confirm that \dls{} 
dominates k-opt for these instances.
\hide{
\setlength{\tabcolsep}{1.5mm}
\begin{table}[htb]
{\scriptsize
\begin{center}
\begin{tabular}{|r|r|r|r|r|}
\hline
&\multicolumn{2}{|c|}{\dls{}} &\multicolumn{2}{|c|}{k-opt{}} \\
\hline
\multicolumn{1}{|c|}{Instance}&\multicolumn{1}{|c|}{Clique size}&
\multicolumn{1}{|c|}{CPU(s)}&\multicolumn{1}{|c|}{Clique size}&
\multicolumn{1}{|c|}{SCPU(s)}\\
\hline \hline
brock400\_2&25(24.69,24)&0.1527&25(24.6,24)&0.280\\
brock400\_4&25&0.0616&25&0.183\\
brock800\_2&21(20.86,20)&1.7235&21(20.8,20)&2.160\\
brock800\_4&21(20.65,20)&1.0058&21(20.5,20)&2.508\\
\hline
C1000.9&67(66.07,64)&0.0373&67(66,65)&6.306\\
C2000.9&77(75.33,74)&0.6317&77(75.1,74)&66.146\\
C4000.5&17&1.3005&17&65.279\\
\hline
keller6&57(55.76,54)&2.6796&57(55.5,55)&125.032\\
\hline
\end{tabular}
\end{center}
}
\vskip -0.2in
\caption{Performance of \dls{} and k-opt where the \dls{} parameter \emph{maxSteps} has been reduced to the point where the clique size results are comparable to those for k-opt. The CPU(s) values for \dls{} include the unsuccessful runs;
\dls{} results are based on 100 runs per instance and k-opt results
on 10 runs per instance.} 
\label{tab:dls-kopt-2}
\vskip -0.1in
\end{table}
\setlength{\tabcolsep}{0.5mm}
}

\setlength{\tabcolsep}{1.0mm}
\begin{table}[htbp]
%\vskip -0.3in
{\scriptsize
\begin{center}
\begin{tabular}{|r|r|r|r|r||r|r|r|r|r|}
\hline
&\multicolumn{2}{|c|}{\dls{}} &\multicolumn{2}{|c||}{k-opt{}} &
&\multicolumn{2}{|c|}{\dls{}} &\multicolumn{2}{|c|}{k-opt{}} \\
\hline
\multicolumn{1}{|c|}{Instance}&\multicolumn{1}{|c|}{Clique size}&
\multicolumn{1}{|c|}{CPU(s)}&\multicolumn{1}{|c|}{Clique size}&
\multicolumn{1}{|c||}{SCPU(s)}&
\multicolumn{1}{|c|}{Instance}&\multicolumn{1}{|c|}{Clique size}&
\multicolumn{1}{|c|}{CPU(s)}&\multicolumn{1}{|c|}{Clique size}&
\multicolumn{1}{|c|}{SCPU(s)}\\
\hline \hline
brock400\_2&25(24.69,24)&0.1527&25(24.6,24)&0.280&C1000.9&67(66.07,64)&0.0373&67(66,65)&6.306\\
brock400\_4&25&0.0616&25&0.183&C2000.9&77(75.33,74)&0.6317&77(75.1,74)&66.146\\
brock800\_2&21(20.86,20)&1.7235&21(20.8,20)&2.160&C4000.5&17&1.3005&17&65.279\\
brock800\_4&21(20.65,20)&1.0058&21(20.5,20)&2.508&keller6&57(55.76,54)&2.6796&57(55.5,55)&125.032\\
\hline
\end{tabular}
\end{center}
}
\vskip -0.2in
\caption{Performance of \dls{} and k-opt where the \dls{} parameter \emph{maxSteps} has been reduced to the point where the clique size results are comparable to those for k-opt. The CPU(s) values for \dls{} include the unsuccessful runs;
\dls{} results are based on 100 runs and k-opt results 
on 10 runs (per instance).} 
\label{tab:dls-kopt-2}
\vskip -0.3in
\end{table}
\setlength{\tabcolsep}{0.5mm}

% [results: tables als-dags and als-kopt]

Finally, Table~\ref{tab:dls-qualex-rls-a} shows performance
results for \dls{} in comparison with results for QUALEX-MS 
from the literature \cite{Busygin02}; the CPU times for QUALEX-MS have been scaled by a factor of 0.64 
to compensate for differences in CPU speed (1.4 GHz Pentium IV CPU \vs{} our 2.2 GHz Pentium IV reference machine).
Using the ranking criteria in Table~\ref{tab:alg-rank-crit}, QUALEX-MS dominates \dls{}
for instances brock400\_1, brock800\_1, brock800\_2 and brock800\_3, while \dls{} dominates QUALEX-MS for the remaining 76 of the 80 DIMACS instances.

\hide{
S. Busygin, A New Trust Region Technique for the Maximum Weight Clique Problem, Submitted to Special Issue of Discrete Applied Mathematics: Combinatorial Optimization 2002.
}%

\setlength{\tabcolsep}{0.7mm}
\begin{table}[htbp]
\vskip -0.3in
{\scriptsize
\begin{center}
\begin{tabular}{|r|r|r|r|r||r|r|r|r|r|}
\hline
&\multicolumn{2}{|c|}{\dls{}}&\multicolumn{2}{|c||}{QUALEX-MS}
&&\multicolumn{2}{|c|}{\dls{}}&\multicolumn{2}{|c|}{QUALEX-MS}\\
\hline
\multicolumn{1}{|c|}{Instance}&\multicolumn{1}{|c|}{Clique size}&\multicolumn{1}{|c|}{CPU(s)}&\multicolumn{1}{|c|}{Clique size}&\multicolumn{1}{|c||}{SCPU(s)}
&\multicolumn{1}{|c|}{Instance}&\multicolumn{1}{|c|}{Clique size}&\multicolumn{1}{|c|}{CPU(s)}&\multicolumn{1}{|c|}{Clique size}&\multicolumn{1}{|c|}{SCPU(s)}\\
\hline \hline
brock200\_1&21&0.0182&21&0.64&johnson32-2-4&16&$<\epsilon$&16&5.12\\
brock200\_2&12&0.0242&12&$<0.64$&johnson8-2-4&4&$<\epsilon$&4&$<0.64$\\
brock200\_3&15&0.0367&15&0.64&johnson8-4-4&14&$<\epsilon$&14&$<0.64$\\
brock200\_4&17&0.0468&17&$<0.64$&keller4&11&$<\epsilon$&11&0.64\\
brock400\_1&27&2.2299&27&1.28&keller5&27&0.0201&26&10.24\\
brock400\_2&29&0.4774&29&1.92&keller6&59&170.4829&53&826.24\\
brock400\_3&31&0.1758&31&1.28&MANN\_a27&126&0.0476&125&0.64\\
brock400\_4&33&0.0673&33&1.28&MANN\_a45&344&51.9602&342&10.88\\
brock800\_1&23&56.4971&23&11.52&MANN\_a81&1098(1097.96,1097)&264.0094&1096&305.28\\
brock800\_2&24&15.7335&24&11.52&MANN\_a9&16&$<\epsilon$&16&$<0.64$\\
brock800\_3&25&21.9197&25&11.52&p\_hat1000-1&10&0.0034&10&17.92\\
brock800\_4&26&8.8807&26&11.52&p\_hat1000-2&46&0.0024&45&21.76\\
C1000.9&68&4.44&64&17.28&p\_hat1000-3&68&0.0062&65&20.48\\
C125.9&34&0.0001&34&$<0.64$&p\_hat1500-1&12&2.7064&12&60.8\\
C2000.5&16&0.9697&16&177.92&p\_hat1500-2&65&0.0061&64&71.04\\
C2000.9&78(77.93,77)&193.224&72&137.6&p\_hat1500-3&94&0.0103&91&69.12\\
C250.9&44&0.0009&44&0.64&p\_hat300-1&8&0.0007&8&0.64\\
C4000.5&18&181.2339&17&1500.8&p\_hat300-2&25&0.0002&25&0.64\\
C500.9&57&0.1272&55&2.56&p\_hat300-3&36&0.0007&35&0.64\\
c-fat200-1&12&0.0002&12&$<0.64$&p\_hat500-1&9&0.001&9&1.92\\
c-fat200-2&24&0.001&24&$<0.64$&p\_hat500-2&36&0.0005&36&2.56\\
c-fat200-5&58&0.0002&58&$<0.64$&p\_hat500-3&50&0.0023&48&2.56\\
c-fat500-1&14&0.0004&14&0.64&p\_hat700-1&11&0.0194&11&6.4\\
c-fat500-10&126&0.0015&126&1.28&p\_hat700-2&44&0.001&44&7.68\\
c-fat500-2&26&0.0004&26&1.28&p\_hat700-3&62&0.0015&62&7.04\\
c-fat500-5&64&0.002&64&1.28&san1000&15&8.3636&15&16.0\\
DSJC1000\_5&15&0.799&14&23.04&san200\_0.7\_1&30&0.0029&30&0.64\\
DSJC500\_5&13&0.0138&13&3.2&san200\_0.7\_2&18&0.0684&18&$<0.64$\\
gen200\_p0.9\_44&44&0.001&42&$<0.64$&san200\_0.9\_1&70&0.0003&70&$<0.64$\\
gen200\_p0.9\_55&55&0.0003&55&0.64&san200\_0.9\_2&60&0.0002&60&0.64\\
gen400\_p0.9\_55&55&0.0268&51&1.28&san200\_0.9\_3&44&0.0015&40&$<0.64$\\
gen400\_p0.9\_65&65&0.001&65&1.28&san400\_0.5\_1&13&0.1641&13&1.28\\
gen400\_p0.9\_75&75&0.0005&75&1.28&san400\_0.7\_1&40&0.1088&40&1.92\\
hamming10-2&512&0.0008&512&24.32&san400\_0.7\_2&30&0.2111&30&1.28\\
hamming10-4&40&0.0089&36&28.8&san400\_0.7\_3&22&0.4249&18&1.28\\
hamming6-2&32&$<\epsilon$&32&$<0.64$&san400\_0.9\_1&100&0.0029&100&1.28\\
hamming6-4&4&$<\epsilon$&4&$<0.64$&sanr200\_0.7&18&0.002&18&0.64\\
hamming8-2&128&0.0003&128&$<0.64$&sanr200\_0.9&42&0.0127&41&$<0.64$\\
hamming8-4&16&$<\epsilon$&16&0.64&sanr400\_0.5&13&0.0393&13&1.28\\
johnson16-2-4&8&$<\epsilon$&8&$<0.64$&sanr400\_0.7&21&0.023&20&1.28\\
\hline
\end{tabular}
\end{center}
}
\vskip -0.2in
\caption{Performance of \dls{} and QUALEX-MS. The SCPU column contains the scaled run-time for QUALEX-MS in CPU seconds;
\dls{} results are based on 100 runs per instance. Using the ranking criteria of this study, QUALEX-MS is the dominant algorithm for instances brock400\_1, brock800\_1, brock800\_2 and brock800\_3, while \dls{} is the dominant algorithm for all other instances.} 
\label{tab:dls-qualex-rls-a}
\vskip -0.3in
\end{table}
\setlength{\tabcolsep}{0.5mm}

\hide{
\cmnt{$\Rightarrow$ hh2: We should say something about the variability of run-time
	in this case (var.coeff.) -- I suspect that since we limit $maxSteps$, it could be quite small
		in many cases, but because \dls{} often finds optimal solutions before the cutoff is reached,
			this is not so clear.}

\cmnt{$\Rightarrow$ FIGURE (MAYBE): corr plots, DAGS vs. \dls{}, k-opt vs. \dls{}
	hh2: I still think it would be very nice to have at least one of these.} \\
}
\clearpage
Overall, the results from these comparative performance evaluations can be 
summarised as follows:
\begin{itemize}
\item QUALEX-MS is dominant for the brock400\_1, brock800\_1, brock800\_2 and brock800\_3 DIMACS instances.
\item RLS is the dominant algorithm for the MANN\_a45 and keller6 DIMACS instances.
\item DAGS is the dominant algorithm for the san1000 DIMACS instance.
\item k-opt is the dominant algorithm for the MANN\_a81 DIMACS instance.
\item \dls{} is the dominant algorithm for the remaining 72 DIMACS instances. 
\end{itemize}
In addition, within the alotted run-time and number of runs,
\dls{} obtained the current best known results for all DIMACS instances
with the exceptions of MANN\_a45 and MANN\_a81.

\section{Discussion}
\label{s:discussion}

%\cmnt{$\Rightarrow$ explore / discuss / explain search behaviour} \\

%hh2: new:
To gain a deeper understanding of the run-time behaviour of \dls{}
and the efficacy of its underlying mechanisms, we performed
additional empirical analyses. 
Specifically, we studied the variability in run-time
between multiple independent runs of \dls{} on the same problem instance;
the role of the vertex penalties in general
and, in particular, the impact of the penalty delay parameter
on the performance and behaviour of \dls{};
and the frequency of pertubation as well as the role of the
perturbation mechanism. 

%hh3: minor revisions:
These investigations were performed using two DIMACS instances, C1000.9 and brock800\_1.
%hh5: minor change in wording:
These instances were selected 
because, firstly, they are of reasonable size and difficulty. Secondly, C1000.9 is a randomly generated instance where the vertices in the optimal maximum clique have predominantly higher vertex degree than the average vertex degree (intuitively it would seem reasonable that, for a randomly generated problem, vertices in the optimal maximum clique would tend to have higher vertex degrees). For brock800\_1, on the other hand, the vertices in the optimal maximum clique have predominantly lower-than-average vertex degree. (Note that the DIMACS brock instances were created in an attempt to defeat greedy algorithms that used vertex degree for selecting vertices~\citeR{Brock96}). 

This fundamental difference is further highlighted by the results of a quantitative analysis of the maximum cliques for these instances, which showed that, for C1000.9, averaged over all maximal cliques found by \dls{}, the average vertex degree of vertices in the maximal cliques is 906 (standard deviation of 9) as compared to 900 (9) when averaged over all vertices; for brock800\_1, the corresponding figures were 515 (11) and 519 (13) respectively.

\subsection{Variability in Run-Time}
\label{sub:rldrtd}

%hh3: new:
The variability of run-time between multiple independent
runs on a given problem is an important aspect of
the behaviour of SLS algorithms such as \dls{}.
Following the methology of Hoos and St\"utzle \citeyear{HooStu04}, we studied this aspect based on run-time distributions (RTDs)
of \dls{} on our two reference instances.

As can be seen from the empirical RTD graphs shown in Figure~\ref{f:dls-rtds}
(each based on 100 independent runs that all reached
the respective best known clique size), 
\dls{} shows a large variability in run-time. 
Closer investigation shows that the RTDs are quite well
approximated by exponential distributions
(a Kolmogorov-Smirnov goodness-of-fit test 
failed to reject the null hypothesis that the 
sampled run-times stem from the exponential distributions 
shown in the figure at a standard confidence level
of $\alpha=0.05$ with p-values between 
$0.16$ and $0.62$).
This observation is consistent with similar results 
for other high-performance SLS
algorithms, \eg{}, for SAT \cite{HooStu00}
and 
%Tabu Search \cite{WatWhiHow05}.
%hh-final: changed to:
scheduling problems \cite{WatWhiHow05}.
As a consequence, performing multiple independent runs
of \dls{} in parallel will result in close-to-optimal parallelisation speedup \cite{HooStu04}. 
Similar observation were made for most of the
other difficult DIMACS instances.

\begin{figure}[!ht]
\vskip -1.2in
\begin{center}
\includegraphics[width=7.0cm]{Figures/rnd-rld.eps}
\hspace*{2mm}
\includegraphics[width=7.0cm]{Figures/rnd-rtd.eps}
\vspace*{5mm}
\includegraphics[width=7.0cm]{Figures/brock-rld.eps}
\hspace*{2mm}
\includegraphics[width=7.0cm]{Figures/brock-rtd.eps}
\end{center}
\vskip -0.2in
\caption{Run-time distributions
	for \dls{} applied to C1000.9
	(top) and brock800\_1 (bottom),
	measured in search steps (left) and CPU seconds (right)
	on our reference machine
	(based on 100 independent runs each of which
	reached the best known clique size);
	these empirical RTDs
	are well approximated by 
	exponential distributions, labelled
	$ed[m](x)=1-2^{-x/m}$ in the plots.}
\label{f:dls-rtds}
\vskip -0.4in
\end{figure}	


\subsection{Penalty Delay Parameter and Vertex Penalties}
\label{s:weighting}

%hh3: some changes:

The penalty delay parameter \emph{pd} specifies the number of penalty increase iterations that must occur in \dls{}
before there is a penalty decrease (by 1) for all vertices that currently have a penalty. For the MAX-CLIQUE problem, \emph{pd} basically provides a mechanism for focusing on lower degree vertices when constructing current cliques. 
With \emph{pd} = 1 (\ie{}, no penalties), the frequency with which vertices are in the improving neighbour / level neighbour sets will basically be 
%hh5: added (for clarity):
solely
dependent on their 
%vertex 
degree. Increasing \emph{pd} overcomes this bias towards higher degree vertices, as it allows their penalty values to increase (as they are more often in the current clique), which inhibits their selection for the current clique. This in turn allows lower degree vertices to become part of the current clique. 
This effect of the penalty delay parameter is illustrated
in Figure~\ref{f:degree-freq}, which shows the 
correlation between the degree of the vertices and their
frequency of being included in the current clique immediately prior
to a perturbation being performed within \dls{}.

\begin{figure}[htb]
\begin{center}
\includegraphics[width=10cm]{Figures/degree_freq}
\end{center}
\vskip -0.2in
\caption{Correlation between the vertex degree and the frequency with which vertices were present in the clique immediately prior to each \dls{} perturbation. For C1000.9 and brock800\_1, with \emph{pd} = 1, the higher degree vertices tend to have a higher frequency of being present in the clique immediately prior to each \dls{} perturbation. For brock800\_1, with \emph{pd} = 45, the frequency of being present in the clique immediately prior to each \dls{} perturbation is almost independent of the vertex degree.}
\label{f:degree-freq}
\vskip -0.1in
\end{figure}	


Currently, \emph{pd} needs to be tuned to a family (or, in the case of the brock instances, a sub-family) of instances. In general, this could be done in a principled way based on RTD graphs, but for \dls{}, which is reasonably robust with regard to the exact value of the parameter (as shown by Figures~\ref{f:brock800.1-delay} and \ref{f:brock800.1-delay-three}), the actual tuning process was a simple, almost interactive process and did not normally require evaluating RTD graphs. 
%hh-final: minor rewording:
Still, fine-tuning based on RTD data could possibly result in further, minor 
performance improvements.

\begin{figure}[htb]
\begin{center}
\includegraphics[width=10cm]{Figures/delay_median_brock800_1}
\end{center}
\vskip -0.2in
%hh-final: minor rewording:
\caption{Success rate and median CPU time of \dls{} as a function of the penalty delay parameter, $pd$, 
for the benchmark instance brock800\_1. Each data point is based on 100 independent
runs.}
\label{f:brock800.1-delay}
\vskip -0.1in
\end{figure}	

\begin{figure}[htb]
\begin{center}
\includegraphics[width=10cm]{Figures/brock800_1_delay_35_45_50}
\end{center}
\vskip -0.2in
\caption{
%Run-length and run-time distributions for \dls{} on brock800\_1 for penalty delays of 35, 45 and 50. 
%hh5: minor change in wording:
%hh-final: added 'top' and 'bottom':
Run-time distributions for \dls{} on brock800\_1 for penalty delays of 35, 45 and 50,
measuring run-time in search steps (top) and CPU seconds (bottom).
%hh-final: minor rewording:
The performance for a penalty delay of 45 clearly dominates that for 35 and 50.}
\label{f:brock800.1-delay-three}
\vskip -0.1in
\end{figure}	
\clearpage
 
The effect of the penalty delay parameter on the vertex penalties 
is clearly illustrated in Figure~\ref{f:brock800.1-num-weight},
which shows cumulative distributions of the number of penalised vertices at each 
perturbation in \dls{}, 
for representative runs of \dls{} on the DIMACS brock800\_1 instance, for varying values of the parameter \emph{pd}.
Note that for brock800\_1, the optimal \emph{pd} value of 45 corresponds to the point where, on average, about 90\% of the vertices have been penalised.
The role of the \emph{pd} parameter is further illustrated in
Figure~\ref{f:node-freq},
which shows the (sorted) frequency with which vertices were present in the current
clique immediately prior to each perturbation for C1000.9 and brock800\_1. 
Note that for both instances, using higher penalty delay settings 
significanly reduces the bias towards including certain
vertices in the current clique. As previously demonstrated,
without vertex penalties (\ie{}, for $pd=1$),
\dls{} prefers to include high-degree vertices in the current clique,
which in the case of problem instances 
like C1000.9, where optimal cliques tend to consist of vertices
with higher-than-average degrees, 
is an effective strategy. In instances such as brock800\_1, however, where 
the optimal clique contains many vertices of 
lower-than-average degree,
the heuristic bias towards high-degree vertices is misleading
and needs to be counteracted, \eg{}, by means of vertex penalties.

\begin{figure}[htb]
\begin{center}
\includegraphics[width=10cm]{Figures/weighted_nodes}
\end{center}
\vskip -0.2in
\caption{Cumulative distributions of the number of penalised vertices
measured at each search perturbation over representative
independent runs
of \dls{} on the DIMACS brock800\_1 instance as the penalty delay parameter 
\emph{pd} is varied (the left most curve corresponds to $pd=5$). 
Note that for the approx.~optimal penalty delay of $pd=45$ (solid line),
on average about 90\% vertices are penalised (\ie{}, have a penalty value greater than zero).}
\label{f:brock800.1-num-weight}
\vskip -0.1in
\end{figure}	

\begin{figure}[htb]
\begin{center}
\includegraphics[width=10cm]{Figures/node_freq}
\end{center}
\vskip -0.2in
\caption{Sorted frequency with which vertices were present in the current 
clique immediately prior to each \dls{} perturbation for C1000.9 (top) and brock800\_1 (bottom),
based on a representative run on each problem instance.
Note that by using penalty delay values $pd>1$,
the bias towards using certain vertices more frequently
than others is substantially reduced.}
\label{f:node-freq}
\vskip -0.1in
\end{figure}	


Generally, by reducing the bias in the cliques visited,
vertex penalties help to diversify the search in \dls{}.
At the same time, penalties do not appear to provide a 
`learning' mechanism through which \dls{} identifies those 
vertices that should be included in the current clique.
This is in agreement with recent results for SAPS,
a high-performance dynamic local search algorithm for SAT
\cite{HooStu04}.


%hh3: major changes:

\subsection{Perturbation Mechanism and Search Mobility}

To prevent search stagnation, \dls{} uses a perturbation
mechanism that is executed whenever its plateau
search procedure has failed to 
lead to a clique that 
can be further expanded.
Since this mechanism 
%hh5: change in wording:
%leads to 
causes 
major changes in the current
clique, it has relatively high time complexity.
It is therefore interesting to investigate how frequently
these rather costly and disruptive perturbation steps are performed.
Figure~\ref{f:selections_c1000} shows the distribution of the 
number of improving search steps (\ie{}, clique expansions)
and plateau steps (\ie{}, vertex swaps)
between successive perturbation phases for a representative run of \dls{} on the C1000.9 instance.
Analogous results for brock800\_1 are shown in 
Figure~\ref{f:selections_brock800}. These figures basically show the result of the 
interactions between the improving and plateau search steps, the perturbation mechanism and the problem structure.

\begin{figure}[htbp]
\vskip -0.2in
\begin{center}
\includegraphics[width=9.5cm]{Figures/selections_c1000}
\end{center}
\vskip -0.2in
\caption{Number of improving search steps and plateau swaps between 
successive perturbation phases of \dls{} for C1000.9.
The graphs show the cumulative distributions of these measures 
collected over representative 
independent runs for each \emph{pd} value;
the solid lines correspond to the approx.~optimal penalty delay for this
instance, $pd=1$.}
\label{f:selections_c1000}
\vskip -0.3in
\end{figure}	
\begin{figure}[htbp]
\begin{center}
\includegraphics[width=9.5cm]{Figures/selections_brock800}
\end{center}
\vskip -0.2in
\caption{Number of improving search steps and plateau swaps between 
successive perturbation phases of \dls{} for brock800\_1.
The graphs show the cumulative distributions of these measures 
collected over representative 
independent runs for each \emph{pd} value;
the solid lines correspond to the approx.~optimal penalty delay for this
instance, $pd=45$.}
\label{f:selections_brock800}
\vskip -0.3in
\end{figure}	
\clearpage
As can be seen from this data, when compared to higher penalty delay values, $pd=1$
results in significantly shorter plateau phases and somewhat
longer improvement phases. At the same time, the differences in the
behaviour of \dls{} observed for various penalty delay values greater
than one are relatively small.
One explanation for this phenomenon lies in the fact that for $pd=1$,
effectively no vertex penalties are used, and consequently,
the selection from the improving and level neighbours sets in each
search step is less constrained.
Intuitively, this should make it easier to find
exits off plateaus in the underlying search landscape
and to follow gradients for a larger number of search steps.

Whether this renders the search more efficient clearly depends on the
topology of the given search landscape.
Instance C1000.9 has at least 70 optimal solutions (see Table~\ref{tab:dls-performance}),
and by construction, these optimal cliques have higher-than-average
vertex degree. This suggests that the respective search landscape has a
relatively high fitness-distance correlation, which would explain why
this problem instance is relatively easy to solve and also why
using the less radical perturbation mechanism associated with $pd = 1$
(which adds a randomly chosen vertex $v$ to the current clique and
removes all vertices not connected to $v$)
provides sufficient diversification to the search process.
Instance brock800\_1, on the other hand, appears to have only
a single optimal solution but many near-optimal solutions (\ie{}, large but
non-optimal cliques that cannot be further extended), since by
construction, its optimal clique has lower-than-average vertex degree.
This suggests that the respective search landscape has
relatively low fitness-distance correlation, and therefore, the more
radical perturbation mechanism used for $pd>1$ (which restarts clique
construction from the most recently added vertex and uses vertex
penalties for diversification) is required in order to obtain good
performance; this hypothesis is also in agreement with the relatively
high cost for solving this problem instance.

To further investigate the efficacy of perturbation in \dls{}
as a diversification mechanism, 
we measured the relative mobility of the search, defined as 
the Hamming distance between the current cliques 
(\ie{}, number of different vertices) at consecutive
perturbations divided by two times the maximum clique size, 
for representative runs of \dls{} on instances C1000.9 and brock800\_1
(this mobility measure is closely related to those used in previous studies \cite{SchSch00}).
As can be seen from Figure~\ref{f:mobility}, 
there is a large difference in mobility between
the two variants of the perturbation mechanism for $pd=1$ and 
$pd > 1$; the former restarts the search from a randomly chosen
vertex and consequently leads to a large variability 
in Hamming distance to the previous clique,
while the latter restarts from the most recently added vertex,
using vertex penalties to increase search diversification,
and hence shows consistently much higher mobility.
Note that when vertex penalties are used (\ie{}, $pd>1$), 
the \emph{pd} value has no significant effect on
search mobility. At the same time, as previously observed
(see Figure~\ref{f:brock800.1-delay}), the performance
of \dls{} does significantly depend on the penalty update delay 
\emph{pd}.
This demonstrates that in order to achieve peak performance,
the increased mobility afforded by
the use of vertex penalties needs to be combined with 
the correct amount of additional diversification achieved
by using a specific penalty update delay.

\begin{figure}[htb]
\begin{center}
\includegraphics[width=10cm]{Figures/mobility}
\end{center}
\vskip -0.2in
\caption{Mobility of search between consecutive perturbation phases in \dls{} for 
instances C1000.9 (top) and brock800\_1 (bottom).
Mobility is measured in terms of relative Hamming distance,
\ie{}, number of different vertices between the respective cliques divided by two times the maximum clique size.
The graphs show the cumulative distributions of relative mobility measurements
collected over representative 
independent runs for each \emph{pd} value and problem instance;
the solid lines correspond to the respective approx.~optimal \emph{pd} values.}
\label{f:mobility}
\vskip -0.1in
\end{figure}	
\hide{old stuff:
As shown in the pseudo-code for \dls{} (Figure~\ref{fig:dls}), periodic restarts are performed during a search.  
The mobility for C1000.9 and brock800\_1 between restarts of \dls{} is shown in Figure~\ref{f:mobility}. Here mobility is defined as the Hamming distance between the current clique at consecutive restarts. For C1000.9 the best known result for the maximum clique size is 68 while that for brock800\_1 is 23. Clearly C1000.9 requires low mobility at each restart which correlates with searching intensively amongst the higher degree vertices that are more likely to be in the optimal maximum clique. For brock800\_1, high mobility is preferable so that the more numerous medium and lower degree vertices are included in the current clique.

For C1000.9 the optimal \emph{pd} is 1 which correlates with an increase in the use of improving search steps to give a rapid increase in the size of the current clique with relatively little effort devoted to searching plateaus. The non-optimal \emph{pd} of 10 places a lot more emphasis on searching plateaus and less on rapidly increasing the size of the current clique. For brock800\_1, Figure~\ref{f:selections_brock800},
the optimal \emph{pd} is 45 which correlates with an increase in the searching of plateaus as compared to the non-optimal values for \emph{pd} of 5 and 35.
}

\hide{
\cmnt{$\Rightarrow$ de-facto tabu mechanism when removing vertices from clique
  - important for performance} \\
\cmnt{$\Rightarrow$ FIGURE: brock800.1, C1000.9 avg distance between cliques between $h$ restarts vs. $h$, d=1,d=2, d=opt/high; problem: distance measure is `too local'} \\
\cmnt{$\Rightarrow$ possibly look at \# of non-unit penalties as function of delay} \\
\cmnt{$\Rightarrow$ coverage: save last k cliques, analyse distributions of differences} \\
\cmnt{$\Rightarrow$ speculation / results on search space structure?}
}


\section{Conclusions and Future Work}

We have demonstrated how by applying the general paradigm of dynamic local search
to the maximum clique problem, the state of the art in MAX-CLIQUE solving
can be improved.
Our new algorithm, \dls{}, has some similarity to previous MAX-CLIQUE
algorithms, in particular to the recently introduced DAGS algorithm:
Both algorithms use vertex penalties to guide the heuristic selection
of vertices when searching for maximum cliques.
However, unlike DAGS, which has an initial phase of unweighted greedy construction search,
\dls{} uses and updates the vertex penalties throughout the entire search process.
Furthermore, weight updates in DAGS are monotone while, in \dls{}, 
vertex penalties are subject to increases as well as to occasional
decreases, which effectively allows the algorithm to `forget' vertex 
penalties over time.
Furthermore, \dls{} selects the vertex to be added to the current clique in
each step solely based on its penalty, while vertex selection 
in DAGS is based on the total weight of the neighbouring vertices
and hence implicitely uses vertex degree for heuristic guidance.
The fact that \dls{}, although conceptually slightly simpler,
outperforms DAGS on all but one of the standard DIMACS benchmark instances
in combination with its excellent performance compared to other
high-performance MAX-CLIQUE algorithms 
clearly demonstrates the value of the underlying paradigm
of dynamic local search with non-monotone penalty dynamics.

The work presented in this article can be extended in several directions.
In particular, it would be interesting to investigate to which 
extent the use of multiplicative penalty update mechanisms in \dls{}
instead of its current additive mechanism can lead to further performance
improvements. We also believe that the current implementation of \dls{}
can be further optimised. For example, for each selection of a vertex to be added to the current clique, our implementation of \dls{} performs a complete scan of either the improving or plateaus sets to build the list of vertices with the lowest penalties;
it would probably be more efficient to maintain this list by means
of an incremental update scheme.
Another very interesting direction for future research is 
to develop mechanisms for automatically adjusting
\dls{}'s penalty delay parameter during the search,
similar to the scheme used for dynamically adapting 
the tabu tenure parameter in RLS \cite{BatPro01}
and Reactive Tabu Search \cite{BatTec94},
%hh3: for ref, see BatPro01
or the mechanism used for controlling the noise
parameter in Adaptive Novelty$^+$ \cite{Hoos02}.
Finally, given the excellent performance of \dls{} 
on standard MAX-CLIQUE instances reported here
suggests that the underlying dynamic local search method
has substantial potential to provide the basis
for high-performance algorithms for other combinatorial
optimisation problems, particularly
weighted versions of MAX-CLIQUE and 
conceptually related clustering problems.

\hide{
\item investigating how \dls{} can be modified so that it becomes the dominant algorithm for the 8 remaining DIMACS instances for which it is not.
\item{} implementation of a parallel version of \dls{}.
\end{itemize}
}

\vspace{0.2in}

\noindent
\acks{The authors would like to thank Liang Zhao for her participation in performing some of the initial experiments for this paper.}
\bibliography{max-clique-final}
\bibliographystyle{theapa}





\hide{
\tablefirsthead{\hline\multicolumn{5}{|c|}{DIMACS CLIQUE
BENCHMARKS}\\\hline File&Code&Nodes&Edges&Clique Size\\\hline}
\tablehead{\hline\multicolumn{5}{|c|}{DIMACS CLIQUE
BENCHMARKS (cont.)}\\\hline File&Code&Nodes&Edges&Clique Size\\\hline}
\tabletail{\hline\multicolumn{5}{|r|}{\it Continued on next
page}\\\hline}
\tablelasttail{\hline}
\begin{supertabular}{|lc|rr|c|}
c-fat200-1.clq&(CFat)&200&1534&\\
c-fat200-2.clq&(CFat)&200&3235&\\
c-fat200-5.clq&(CFat)&200&8473&\\
c-fat500-1.clq&(CFat)&500&4459&\\
c-fat500-10.clq&(CFat)&500&46627&\\
c-fat500-2.clq&(CFat)&500&9139&\\
c-fat500-5.clq&(CFat)&500&23191&\\
johnson16-2-4.clq&(Joh)&120&5460&8\\
johnson32-2-4.clq&(Joh)&496&107880&\\
johnson8-2-4.clq&(Joh)&28&210&\\
johnson8-4-4.clq&(Joh)&70&1855&14\\
keller4.clq&(Kel)&171&9435&11\\
keller5.clq&(Kel)&776&225990&27\\
keller6.clq&(Kel)&3361&4619898&$\ge$ 59\\
hamming10-2.clq&(Ham)&1024&518656&\\
hamming10-4.clq&(Ham)&1024&434176&\\
hamming6-2.clq&(Ham)&64&1824&32\\
hamming6-4.clq&(Ham)&64&704&4\\
hamming8-2.clq&(Ham)&256&31616&$\ge$ 79\\
hamming8-4.clq&(Ham)&256&20864&16\\
san1000.clq&(San)&1000&250500&15\\
san200\_0.7\_1.clq&(San)&200&13930&30\\
san200\_0.7\_2.clq&(San)&200&13930&18\\
san200\_0.9\_1.clq&(San)&200&17910&70\\
san200\_0.9\_2.clq&(San)&200&17910&60\\
san200\_0.9\_3.clq&(San)&200&17910&44\\
san400\_0.5\_1.clq&(San)&400&39900&13\\
san400\_0.7\_1.clq&(San)&400&55860&40\\
san400\_0.7\_2.clq&(San)&400&55860&30\\
san400\_0.7\_3.clq&(San)&400&55860&22\\
san400\_0.9\_1.clq&(San)&400&71820&100\\
sanr200\_0.7.clq&(San)&200&13868&\\
sanr200\_0.9.clq&(San)&200&17863&\\
sanr400\_0.5.clq&(San)&400&39984&\\
sanr400\_0.7.clq&(San)&400&55869&\\
brock200\_1.clq.b&(Bro)&200 &14834 &21 \\
brock200\_2.clq.b&(Bro)&200 &9876 &12 \\
brock200\_3.clq.b&(Bro)&200 &12048 &15 \\
brock200\_4.clq.b&(Bro)&200 &13089 &17 \\
brock400\_1.clq.b&(Bro)&400 &59723 &27 \\
brock400\_2.clq.b&(Bro)&400 &59786 &29 \\
brock400\_3.clq.b&(Bro)&400 &59681 &31 \\
brock400\_4.clq.b&(Bro)&400 &59765 &33 \\
brock800\_1.clq.b&(Bro)&800 &207505 &23 \\
brock800\_2.clq.b&(Bro)&800 &208166 &24 \\
brock800\_3.clq.b&(Bro)&800 &207333 &25 \\
brock800\_4.clq.b&(Bro)&800 &207643 &26 \\
p\_hat300-1.clq&(PHat)&300 &10933 & \\
p\_hat300-2.clq&(PHat)&300 &21928 & \\
p\_hat300-3.clq&(PHat)&300 &33390 & \\
p\_hat500-1.clq&(PHat)&500 &31569 & \\
p\_hat500-2.clq&(PHat)&500 &62946 & \\
p\_hat500-3.clq&(PHat)&500 &93800 & \\
p\_hat700-1.clq&(PHat)&700&60999& \\
p\_hat700-2.clq&(PHat)&700&121728& \\
p\_hat700-3.clq&(PHat)&700&183010& \\
p\_hat1000-1.clq&(PHat)&1000 &122253 & \\
p\_hat1000-2.clq&(PHat)&1000 &244799 & \\
p\_hat1000-3.clq&(PHat)&1000 &371746 & \\
p\_hat1500-1.clq&(PHat)&1500 &284923 & \\
p\_hat1500-2.clq&(PHat)&1500 &568960 & \\
p\_hat1500-3.clq&(PHat)&1500 &847244 & \\
MANN\_a27.clq&(Stein)&378&70551&126\\
MANN\_a45.clq&(Stein)&1035&533115&345\\
MANN\_a81.clq&(Stein)&3321&5506380&$\ge$1100\\
MANN\_a9.clq&(Stein)&45&918&16\\
\end{supertabular}

\bigskip
\noindent {\bf Notes:}

\begin{description}
\item[CFat] (From Panos Pardalos {\tt pardalos@math.uflorida.edu})
Problems based on fault diagnosis problems.  Original reference is
Berman and Pelc, `Distributed Fault Diagnosis for Multiprocessor
Systems,' {\it Proceedings of the 20th Annual Symposium on
Fault--Tolerant Computing}, 340--346 (1990).  For more instances, see
the generator in graph/contributed/pardalos.

\item[Joh] (From Panos Pardalos {\tt pardalos@math.uflorida.edu})
Problems based on problem in coding theory.  A Johnson graph with
parameters $n, w, d$ has a node for every binary vector of length $n$
with exactly $w$ 1s.  Two vertices are adjacent if and only if their
hamming distance is at least $d$.  A clique then represents a feasible
set of vectors for a code.  For more instances, see
the generator in graph/contributed/pardalos.

\item[Kel] (From Peter Shor {\tt shor@research.att.com}) Problems
based on Keller's conjecture on tilings using hypercubes.  One
reference is J.C. Lagarias and P.W. Shor, `Keller's Cube--Tiling
Conjecture is False in High Dimensions,' {\it Bulletin of the AMS},
{\bf 27:} 279--283 (1992). For more instances (though they get very
large very fast) see either the generator in graph/contributed/shor or
the generator in graph/contributed/pardalos.

\item[Ham] (From Panos Pardalos {\tt pardalos@math.uflorida.edu})
Another coding theory problem.  A Hamming graph with parameters $n$
and $d$ has a node for each binary vector of length $n$.  Two nodes
are adjacent if and only if the corresponding bit vectors are hamming
distance at least $d$ apart.  For more instances, see
the generator in graph/contributed/pardalos.  It has been noted by
participants that $n--2$ graphs have a maximum clique of size
$2^{n-1}$.  For a proof of this, see the note in
graph/contributed/bourjolly/hamming.tex. 

\item[San] (From Laura Sanchis {\tt laura@cs.colgate.edu}) Instances
based on her `Test Case Construction for Vertex Cover Problem,'
DIMACS Workshop on Computational Support for Discrete Mathematics,
March 1992 along with more recent work that will be part of a
technical report to be published.  The generator generates instances
with known clique size.

\item[SanR] (From Laura Sanchis {\tt laura@cs.colgate.edu}) These
are random instances with sizes similar to those in {\bf San}.

\item[Bro] (From Mark Brockington {\tt brock@cs.ualberta.ca})
Instances from Mark Brockington and Joe Culberson's generator that
attempts to `hide' cliques in a graph where the expected clique size
is much smaller.  For more instances, see their generator in
graph/contributed/brockington.  

\item [PHat] (From Patrick Soriano and Michel Gendreau 
               {\tt  patrick@crt.umontreal.ca})
     Random problems generated with the p\_hat generator which is a 
     generalization of the classical uniform random graph generator. Uses
     3 parameters: $n$, the number of nodes, and $a$ and $b$, two density 
     parameters verifying $0 \le a \le b \le 1$. Generates problem instances 
     having wider node degree spread and larger clique sizes. Reference: 
     "Solving the Maximum Clique Problem Using a Tabu Search Approach", 
     {\em Annals of Operations Research} {\bf 41}, 385--403 (1993).

\item[Stein] (From Carlo Mannino {\tt mannino@iasi.rm.cnr.it}) Clique
formulation of the set covering formulation of the Steiner Triple
Problem.  Created using Mannino's code to convert set covering
problems to clique problems.

\end{description}
}

\end{document}
