A Memetic Approach for the Max-Cut Problem

Qinghua Wu and Jin-Kao Hao

Abstract. The max-cut problem is to partition the vertices of a weighted graph G = (V,E) into two subsets such that the weight sum of the edges crossing the two subsets is maximized. This paper presents a memetic max-cut algorithm (MACUT) that relies on a dedicated multi-parent crossover operator and a perturbation-based tabu search procedure. Experiments on 30 G-set benchmark instances show that MACUT competes favorably with 6 state-of-the-art max-cut algorithms, and for 10 instances improves on the best known results ever reported in the literature.

Keywords: Multi-parent crossover, memetic algorithm, local search, graph partitioning

LNCS 7492, p. 297 ff.

Full article in PDF | BibTeX

lncs@springer.com
© Springer-Verlag Berlin Heidelberg 2012