%I can be reached at the following e-mail address: borchers@nmt.edu 
\documentstyle{article}
\begin{document}
\newtheorem{algorithm}{Algorithm}
\title{}
\author{Brian Borchers}
\date{December 11, 1992}
\maketitle
This document describes three proposed heuristics for the maximum 
independent set problem.  The heuristics will be tested on a variety
of large independent set problems and maximum clique problems 
in hopes of answering the following questions:
\begin{itemize}
\item How good are the heuristics at finding solutions to the 
maximum independent set problem?  Are more sophisticated techniques
based on Tabu Search, Simulated Annealing, etc. able to produce
better solutions?  
\item Maximum clique problems can be solved by finding a maximum independent
set on the complement of the original graph.  Are these heuristics 
effective in solving maximum clique problems?  
\end{itemize}

Our first heuristic is a very simple greedy heuristic.  The algorithm 
generates a random permutation of the $n$ nodes in the graph.  It then
loops through the nodes, adding a node to its solution if none of the 
neighbors of that node are already in the solution.  The random permutation
of the nodes is stored in an array $P$.  The solution is stored in 
an array $Soln$.  $Soln(i)$ is $1$ if node $i$ is in the solution and $0$ if 
node $i$ is not in the solution.      The algorithm also
maintains a table, $Coverage$.  After each iteration of the algorithm, 
$Coverage(i)$ gives the number of neighbors of node $i$ that are in 
the current solution.  

\begin{algorithm} \mbox{\hspace{0.5in}} \\
\begin{verbatim}
for i=1 to n do
  Coverage(i)=0
  Soln(i)=0
enddo

Construct a random permutation of the numbers 1,2, ..., n and store it 
in the array P. 

for j=1 to n do
  i=P(j)
  if (Coverage(i)=0) then
    Soln(i)=1
    for k in Neighbors(i) do
      Coverage(k)=Coverage(k)+1
    enddo
  endif
enddo
\end{verbatim}
\end{algorithm}
 
The greedy heuristic is proposed mainly as a way to generate a reasonably
good solution that can be used to start the remaining heuristics, which
are both of the ``local search'' type.  
 
Our second heuristic is a local search heuristic based on a simple
move.  If $Coverage(i)$ is 1, then we can find the node $j$ which
is in the solution and which covers node $i$.   The local search heuristic
then sets $Soln(i)=1$ and $Soln(j)=0$.  Once we have made this move, 
we apply the greedy heuristic to all neighbors of node $j$.  Clearly, 
the size of the solution will increase or at least remain constant 
after each move.  

Since it is possible for this heuristic to 
oscillate between solutions without improvement, we must decide
when to stop the algorithm.  The algorithm could be run for a fixed
number of iterations or until a fixed number of iterations have 
passed without improvement.  

To help avoid oscillation, the process of searching for a node 
with Coverage(i)=1 should be randomized.  Another possibility is to 
use a tabu list to avoid moves which would return to a previous solution.  

\begin{algorithm} \mbox{\hspace{0.5in}} \\
\begin{verbatim}
Given a solution, along with a coverage table.  

forever do

    Find a node i with Coverage(i)=1.
    Find j such that i is a neighbor of j and Soln(j)=1.
    Soln(i)=1.
    Soln(j)=0.
    Apply the greedy heuristic to all nodes in Neighbors(j).
    Update the Coverage table.  

enddo
\end{verbatim}
\end{algorithm}
 
The third heuristic searches for sets of four nodes $i$, $j$, $k$, and $l$
with the following properties:
\begin{itemize}
\item $Soln(i)=1$, $Soln(j)=1$, $Soln(k)=0$, and $Soln(l)=0$.
\item Nodes $k$ and $l$ are both covered by nodes $i$ and $j$ and by 
no other nodes in the solution.
\end{itemize}
In this case, 
we can let $Soln(i)=0$,  $Soln(j)=0$, $Soln(k)=1$, and $Soln(l)=1$.  After
recomputing the $Coverage$ table, we apply the greedy heuristic to the 
neighbors of nodes $i$ and $j$.  

\begin{algorithm} \mbox{\hspace{0.5in}} \\
\begin{verbatim}
Given a solution, along with a coverage table.  

forever do
  Find a set of four nodes satisfying the above conditions.  

  Soln(i)=0
  Soln(j)=0
  Soln(k)=1
  Soln(1)=1

  Update the Coverage table.

  Apply the greedy heuristic to Neighbors(i) and Neighbors(j).

enddo
\end{verbatim}
\end{algorithm}

Again, we need a mechanism for deciding when to terminate the search.
We will also look for ways to avoid returning to previous solutions.  
\end{document}

 

\bibliographystyle{plain}
\bibliography{nodepack}