Neural Networks and NP-complete Optimization Problems; A Performance Study on the Graph Bisection Problem
Carsten Peterson
James R. Anderson
Microelectronics and Computer Technology Corporation,
3500 West Balcones Center Drive, Austin, TX 78759-6509, USA
Abstract
The performance of a mean field theory (MFT) neural network technique for finding approximate solutions to optimization problems is investigated for the case of the minimum cut graph bisection problem, which is NP-complete. We address the issues of solution quality, programming complexity, convergence times and scalability. Both standard random graphs and more structured geometric graphs are considered. We find very encouraging results for all these aspects for bisection of graphs with sizes ranging from 20 to 2000 vertices. Solution quality appears to be competitive with other methods, and the effort required to apply the MFT method is minimal. Although the MFT neural network approach is inherently a parallel method, we find that the MFT algorithm executes in less time than other approaches even when it is simulated in a serial manner.
