DSLS: a simple and efficient local search algorithm for the maximum bisection problem

The maximum bisection problem (max-bisection) belongs to a family of well-known graph partitioning problems with wide applications. In this study, we develop a simple and efficient local search algorithm called DSLS for max-bisection. The main idea in DSLS is the dynamic step strategy, which automatically adjusts the intensification and diversification to complete the search by changing the length of the step. Moreover, we design an efficient initial constructive method based on the degree information of the vertices, which provides high-quality initial solutions to the DSLS algorithm. In the data preprocessing, a reduction rule is proposed to cut down the size of benchmark graphs and improve the performance of the DSLS algorithm on benchmark graphs. We adopt 71 well-known benchmark graphs to evaluate our algorithm, and the experiments show that the DSLS algorithm is highly competitive with the state-of-the-art heuristic algorithms and discovers improved best-known results (new lower bounds) for 12 benchmark graphs.