A Binary Neural Network Approach for Max Cut Problems

摘要

The max cut problem of a graph G(V, E) is to find a partition of V into two disjoint subsets such that the sum of weights of cut edges in E is maximized. This paper presents a binary neural network for this NP-complete problem, which is suitable for the hardware implementation on digital circuits. The shaking term is newly introduced in order to drastically improve the performance. The simulation results in weighted complete graphs and unweighted random graphs with up to 1000 vertices show that the binary neural network provides the satisfactory solution quality as compared to the latest algorithm.