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

详细信息    查看全文

• 作者：Fuda Ma ; Jin-Kao Hao
• 关键词：Max ; k ; cut and max ; cut ; Graph partition ; Multiple search strategies ; Tabu list ; Heuristics
• 刊名：Annals of Operations Research
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：248
• 期：1-2
• 页码：365-403
• 全文大小：
• 刊物类别：Business and Economics
• 刊物主题：Operation Research/Decision Theory; Combinatorics; Theory of Computation;
• 出版者：Springer US
• ISSN：1572-9338
• 卷排序：248

文摘

The max-k-cut problem is to partition the vertices of an edge-weighted graph \(G = (V,E)\) into \(k\ge 2\) 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 \(k=2\). 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 \(k\in [3,5]\). For the popular special case \(k=2\) (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.