A multiple search operator heuristic for the max-k-cut problem

作者：Ma Fuda; Hao Jin Kao^*

来源：Annals of Operations Research, 2017, 248(1-2): 365-403.

DOI：10.1007/s10479-016-2234-0

• Max-k-cut and max-cut
• Graph partition
• Multiple search strategies
• Tabu list
• Heuristics

The max-k-cut problem is to partition the vertices of an edge-weighted graph into disjoint subsets such that the weight sum of the edges crossing the different subsets is maximized. The problem is referred as the max-cut problem when . In this work, we present a multiple operator heuristic (MOH) for the general max-k-cut problem. MOH employs five distinct search operators organized into three search phases to effectively explore the search space. Experiments on two sets of 91 well-known benchmark instances show that the proposed algorithm is highly effective on the max-k-cut problem and improves the current best known results (lower bounds) of most of the tested instances for . For the popular special case (i.e., the max-cut problem), MOH also performs remarkably well by discovering 4 improved best known results. We provide additional studies to shed light on the key ingredients of the algorithm.

• 出版日期2017-1