Abstract:

Given an undirected graph with edge weights, the max-cut problem is to find a
partition of the vertices into twosubsets, such that the sumof theweights of the edges crossing
different subsets ismaximized.Heuristics based on auxiliary function can obtain high-quality
solutions of the max-cut problem, but suffer high solution cost when instances grow large. In
this paper, we combine clustered adaptive multistart and discrete dynamic convexized
method to obtain high-quality solutions in a reasonable time. Computational experiments on
two sets of benchmark instances from the literature were performed. Numerical results and
comparisons with some heuristics based on auxiliary function show that the proposed
algorithm is much faster and can obtain better solutions. Comparisons with several state-ofthe-
science heuristics demonstrate that the proposed algorithm is competitive.

Key words: Max-cut  Local search  ｜ Dynamic convexized method ｜ Clustered , adaptive multistart