ON THE PERFORMANCE GUARANTEE OF NEURAL NETWORKS FOR NP-HARD OPTIMIZATION PROBLEMS

We give polynomial size threshold neural networks and encoding formali sms, which guarantee worst case performance for two hard optimization problems. We show that a massively parallel algorithm based on such ne ural network models guarantee an approximation ratio, asymptotically e qual to DELTA/2 for the maximum independent set problem, where DELTA i s the maximum degree of the graph, and equal to 2 for the vertex cover ing problem. These results on the power of polynomial size threshold n eural networks within polynomial number of neural updates provide the first approximation results for neural network models.