.png){kind=icon}
返回
Approximation and Parameterized Runtime Analysis of Evolutionary Algorithms for the Maximum Cut Problem
.png){kind=icon}
PRE
AI
DOI：10.1109/TCYB.2014.2354343.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
The maximum cut (MAX-CUT) problem is to find a bipartition of the vertices in a given graph such that the number of edges with ends in different sets reaches the largest. Though, several experimental investigations have shown that evolutionary algorithms (EAs) are efficient for this NP-complete problem, there is little theoretical work about EAs on the problem. In this paper, we theoretically investigate the performance of EAs on the MAX-CUT problem. We find that both the (1+1) EA and the (1+1) EA*, two simple EAs, efficiently achieve approximation solutions of (m/2) + (1/4) s(G) and (m/2) + (1/2)(root 8m + 1 - 1), where m and s(G) are respectively the number of edges and the number of odd degree vertices in the input graph. We also reveal that for a given integer k the (1+ 1) EA* finds a cut of size at least k in expected runtime O(nm + 1/delta(4k)) and a cut of size at least (m/2) + k in expected runtime O(n(2)m + 1/delta((64/3)k2)), where delta is a constant mutation probability and n is the number of vertices in the input graph. Finally, we show that the (1+ 1) EA and the (1+ 1) EA* are better than some local search algorithms in one instance, and we also show that these two simple EAs may not be efficient in another instance.
Keyword:
Approximation performance
evolutionary algorithm (EA)
local search
maximum cut (MAX-CUT) problem
runtime analysis
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
10.5
论文数:
1.1W
被引数:
5.0W
机构
引用论文
.png){kind=icon}
查看更多内容