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

Xinliang Tian, Dantong Ouyang, Huisi Zhou, Rui Sun and Liming Zhang ()
Additional contact information
Xinliang Tian: Jilin University
Dantong Ouyang: Jilin University
Huisi Zhou: Jilin University
Rui Sun: Jilin University
Liming Zhang: Jilin University

Journal of Heuristics, 2024, vol. 30, issue 1, No 2, 43-65

Abstract: Abstract 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.

Keywords: Max-bisection; Graph partitioning problem; Local search; Heuristics (search for similar items in EconPapers)
Date: 2024
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10732-023-09521-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:30:y:2024:i:1:d:10.1007_s10732-023-09521-y

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-023-09521-y

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().