Back to Search Start Over

Evolutionary Algorithm on General Cover with Theoretically Guaranteed Approximation Ratio.

Authors :
Zhang, Yaoyao
Zhu, Chaojie
Tang, Shaojie
Ran, Yingli
Du, Ding-Zhu
Zhang, Zhao
Source :
INFORMS Journal on Computing; Mar/Apr2024, Vol. 36 Issue 2, p510-525, 16p
Publication Year :
2024

Abstract

Theoretical studies on evolutionary algorithms have developed vigorously in recent years. Many such algorithms have theoretical guarantees in both running time and approximation ratio. Some approximation mechanism seems to be inherently embedded in many evolutionary algorithms. In this paper, we identify such a relation by proposing a unified analysis framework for a global simple multiobjective evolutionary algorithm (GSEMO) and apply it on a minimum weight general cover problem, which is general enough to subsume many important problems including the minimum submodular cover problem in which the submodular function is real-valued, and the minimum connected dominating set problem for which the potential function is nonsubmodular. We show that GSEMO yields theoretically guaranteed approximation ratios matching those achievable by a greedy algorithm in expected polynomial time when the potential function g is polynomial in the input size and the minimum gap between different g-values is a constant. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: This work was supported by National Natural Science Foundation of China [11771013, U20A2068]; Zhejiang Provincial Natural Science Foundation of China [LD19A010001]. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
10919856
Volume :
36
Issue :
2
Database :
Complementary Index
Journal :
INFORMS Journal on Computing
Publication Type :
Academic Journal
Accession number :
176567445
Full Text :
https://doi.org/10.1287/ijoc.2022.0327