期刊
ENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE
卷 26, 期 3, 页码 1162-1173出版社
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.engappai.2012.09.001
关键词
Max-Cut; Local search and heuristics; Adaptive diversification; Metaheuristics
类别
资金
- Region of Pays de la Loire, France
Given an undirected graph G=(V,E) where each edge of E is weighted with an integer number, the maximum cut problem (Max-Cut) is to partition the vertices of V into two disjoint subsets so as to maximize the total weight of the edges between the two subsets. As one of Karp's 21 NP-complete problems, Max-Cut has attracted considerable attention over the last decades. In this paper, we present Breakout Local Search (BLS) for Max-Cut. BLS explores the search space by a joint use of local search and adaptive perturbation strategies. The proposed algorithm shows excellent performance on the set of well-known maximum cut benchmark instances in terms of both solution quality and computational time. Out of the 71 benchmark instances, BLS is capable of finding new improved results in 34 cases and attaining the previous best-known result for 35 instances, within computing times ranging from less than 1 s to 5.6 h for the largest instance with 20,000 vertices. (C) 2012 Elsevier Ltd. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据