Report on optimization using NNs and KC

[Arun Jagota]

             *** DO NOT POST TO OTHER BULLETIN BOARDS ***

The following report may be of interest for:
* Combinatorial Optimization (Maximum Clique) via neural nets
* Kolmogorov Complexity; Universal Prior Distribution; generating "hard" 
  instances for optimization problems
* A scheme for generating compressible binary vectors motivated by Kolmogorov 
  Complexity ideas. Source code is offered and may be used to generate 
  compressible test data for any application whose instances directly or 
  indirectly utilize binary vectors; comparison of performance on such test 
  data vs, say, data from the uniform distribution may be useful, as below. 
--------

          Performance of MAX-CLIQUE Approximation Heuristics 
           Under Description-Length Weighted Distributions

	       Arun Jagota             Kenneth W. Regan

                         Technical Report
		   Department of Computer Science
              State University at New York at Buffalo

We study the average performance of several neural-net heuristics applied to 
the problem of finding the size of the largest clique in an undirected graph. 
This function is NP-hard even to approximate within a constant factor in the 
worst case, but the heuristics we study are known to do quite well on average 
for instances drawn from the uniform distribution on graphs of size n. We 
extend a theorem of M. Li and P. Vitanyi to show that for instances drawn from 
the "universal distribution" m(x), the average-case performance of any 
approximation algorithm has the same order as its worst-case performance.
The universal distribution is not computable or samplable. However, we give a 
realistic analogue q(x) which lends itself to efficient empirical testing. Our 
results so far are: out of nine heuristics we tested, three did markedly worse 
under q(x) than under uniform distribution, but six others revealed little 
change. 


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

<file>: KCC.ps, KCC.dvi    (*Same but some people have had problems printing
			     our postscript in the past. `KCC.dvi' may require 
			     `binary' mode in ftp *)

<file>: nlt.README         (* Contains documentation and instructions for 
			      our compressible string generation code *)

If ftp is a problem, the report may also be obtained by sending e-mail to
jagota at cs.buffalo.edu

Arun Jagota

     *** DO NOT POST TO OTHER BULLETIN BOARDS ***