\documentstyle[12pt]{article}

\setlength{\topmargin}{-11mm}
\setlength{\oddsidemargin}{0mm}
\setlength{\evensidemargin}{0mm}
\setlength{\textheight}{225mm}
\setlength{\textwidth}{160mm}

\begin{document}

\title{Ramsey Algorithms and Their Implementations}
\author{Marcus Peinado \hspace{30mm} Steve Homer\\
	mpe@cs.bu.edu \hspace{30mm} homer@cs.bu.edu\\
	Department of Computer Science\\Boston University}
\maketitle

We propose to study approximation algorithms based on subgraph
elimination methods. Such 
algorithms were studied by Boppana and Halld\'{o}rsson in
\cite{boha:90} and  currently have the best 
performance guarantee ($O(n/\log^2 n)$)
for approximating the clique problem .
It is also shown by Boppana and Halld\'{o}rsson that
no algorithm of this kind, that is based entirely on subgraph exclusion,
can achieve a better performance guarantee. 

One of our goals is to construct and characterize graphs that are
{\em hard} for all Ramsey-type/subgraph-exclusion algorithms, where
hard means that the algorithm does not perform
better than its worst case performance guarantee. 
We will begin by considering the particular algorithms 
based on Ramsey's Theorem in \cite{boha:90} and then
consider more general subgraph exclusion algorithms.
The problem can be attacked analytically or by simulations.

An analytical result would be a characterization of a class of graphs
and a proof that the performance ratio of subgraph-exclusion
algorithms on graphs from this class has some lower bound
$l \leq O(n/\log n)$. 

A simulation result would involve implementing several
subgraph-exclusion algorithms
and recording their performance on graphs from the class which we believe
to be hard. Furthermore, the performance of subgraph-exclusion
algorithms on these graphs
could be compared with the performances of different algorithms. As part
of this approach, we will try to parallelize the
subgraph-exclusion algorithm described
in \cite{boha:90} and implement it on the Connection Machine 5. 
We hope to see if subgraph-exclusion algorithms behave differently with
highly parallel implementations, particularly on the hard instances
we find. Finally,
we might look at the effects that randomization has on the performance of
subgraph-exclusion algorithms like those proposed in \cite{boha:90}.
While we will focus on the clique problem first,
we will also consider graph coloring and other NP-hard problems
for which subgraph exclusion techniques are known to apply.

We then plan to try to find algorithms which are
tailored for the class of hard instances we find.
Since the algorithms already known are optimal
among subgraph exclusion algorithms, we plan to look at other types of
algorithms for improved performance on these instances.
One type of algorithm we will try is
simulated annealing or similar Markov chain based algorithms.
We will pay special attention to the design of the neighborhood
structure. There is theoretical \cite{jerrum:92} and experimental
evidence that the performance of simulated annealing is limited if
the standard neighborhood structures are used that change only
one (or few) nodes in each step. It has been observed for other
problems that radically different neighborhood structures, although
harder to analyze, can, in practice, speed up the convergence rate
of the underlying Markov chain significantly.
 One possible source of interesting neighborhood
structures comes from the recent characterizations of NP in terms
of interactive proof classes, see  \cite{ALMSS92}. A neighborhood structure
suggested by the reduction given there is worth considering.

%\bibliographystyle{plain}
%\bibliography{dimacs}

\begin{thebibliography}{1}

\bibitem{ALMSS92}
S.~Arora, C.~Lund, R.~Motwani, M.~Sudan, and M.~Szegedy.
\newblock Proof verification and hardness of approximation problems.
\newblock In {\em Proceedings 33rd {IEEE} {S}ymposium on the {F}oundations of
  {C}omputer {S}cience}, pages 14--23, Los Angeles, CA, 1992. IEEE Computer
  Society.

\bibitem{boha:90}
R.~Boppana and M.~Halld\'{o}rsson.
\newblock Approximating maximum independent sets by excluding subgraphs.
\newblock In {\em SWAT}, pages 11--25. Springer Verlag, 1990.

\bibitem{jerrum:92}
Mark Jerrum.
\newblock Large cliques elude the metropolis process.
\newblock {\em Random Structures and Algorithms}, 3(4):347--360, 1992.

\end{thebibliography}

\end{document}