Neural Network Heuristics for the Maximum Clique Problem

	                  Arun Jagota
	  Department of Computer Science, SUNY/Buffalo, 
	  	    jagota@cs.buffalo.edu

We have employed neural network heuristics such as mean field annealing,
continuous Hopfield dynamics, steepest descent, rho-annealing, and stochastic
dynamics towards approximating Maximum Clique on three distributions of graphs 
(see [1,2]). 

In the remaining 8 months of the challenge, I propose to be involved in 
extending this work in several ways: 
(i)   Test on new distributions supplied by DIMACS or other researchers 
(ii)  Attempt to improve some of the heuristics or their implementations
(iii) Discover new neural net heuristics or evaluate previously untried ones
(iv) Perform empirical comparisons with other approaches.

Since this will be an evolving process, at this time, I do not specify any
more detail. My main objective here is to provide only enough information so 
that others interested in the heuristics that I have studied or the generators 
can get in touch with me and we can decide on the work and divide it up. I 
encourage interested people to get in touch with me for further discussion. I 
also encourage people who are working on similar approaches to get in touch 
with me for further discussion.

1. @inproceedings{Jag92a,
       author = "Jagota, A.",
        title = "Efficiently Approximating Max-Clique in a Hopfield-style Network",
        pages = "248--253",
    booktitle =  "International Joint Conference on Neural Networks",
       volume =  2,
 organization = "Baltimore, June",
    publisher = "IEEE",
      address = "New York",
	 month= "June",
         year =  1992
  }

2. @techreport{JaR92,
       author = "Jagota, A. and K.W. Regan",
        title = "Performance of MAX-CLIQUE Heuristics under Description-length Weighted Distributions",
  institution = "Department of Computer Science, SUNY at Buffalo",
      address = "Buffalo, NY",
      month   = "September",
      number  = "92-24",
      note    = "Available from author",
         year =  1992
  }

Latex source of 1 and postscript or ".dvi" of 2 are, I believe, available
from the challenge "pub" directory.

They are also available as follows:

ftp ftp.cs.buffalo.edu (or 128.205.32.9 subject-to-change)
Name : anonymous
> cd users/jagota
> get <file>
> quit

where file = 
ijcnn92.tex     (* Source of 1 *)
KCC.{ps,dvi},   (* Source of 2 *)
nlt.README, nlt.progs.shar, nlt_source.shar (* Source of "compressible" graphs
					       generator; also includes 
					       Mathematica code of two 
					       heuristics *)

HcN_opt.shar   (* shar file of C code of all heuristics; WARNING: Code
		  is quite large and somewhat unmaintainable; the heuristics
		  implementation is part of larger program developed for
		  other purposes *)

HcN_opt.shar is not available in challenge directories.