Application of the random neural network model to NP-Hard problems

[Erol Gelenbe]

We are doing work on the application of the random neural network
model, introduced in two recent papers of the journal Neural Computation
(E. Gelenbe : Vol. 1,No 4, and Vol. 2, No. 2), to combinatorial
optmisation problems.

Our first results concern the Graph Covering problem. We have considered
400 graphs drawn at random, with 20, 50 and 100 nodes. Over this sample
we observe that :

- The random neural network solution (which is purely analytic, i.e. not
simulated as with the Hopfield network) provides on the average better
results than the usual heuristic (the greedy algorithm), and considerably
better results than the Hopfield-Tank approach.
- The random neural network solution is more time consuming than the greedy
algorithm, but considerably less time consuming than the Hopfield-Tank
approach.

A report can be obtained by writing, or e-mailing me :

erol at ehei.ehei.fr

Erol Gelenbe
EHEI
45 rue des Saints-Peres
75006 Paris, France