.png){kind=icon}
Return
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}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
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.
Keywords:
Approximation performance
evolutionary algorithm (EA)
local search
maximum cut (MAX-CUT) problem
runtime analysis
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
10.5
Papers:
1.1W
Citations:
5.0W
Organization
Cited Papers
.png){kind=icon}
ShareSave
ShareSaveShareSaveShareSaveShareSaveShareSaveShareSave
View more