Evolutionary Algorithm on General Cover with Theoretically Guaranteed Approximation Ratio

Yaoyao Zhang (), Chaojie Zhu (), Shaojie Tang (), Yingli Ran (), Ding-Zhu Du () and Zhao Zhang ()
Additional contact information
Yaoyao Zhang: College of Mathematics and System Science, Xinjiang University, Urumqi, Xinjiang 830046, China
Chaojie Zhu: School of Mathematical Sciences, Zhejiang Normal University, Jinhua, Zhejiang 321004, China
Shaojie Tang: Naveen Jindal School of Management, University of Texas at Dallas, Richardson, Texas 75080
Yingli Ran: School of Mathematical Sciences, Zhejiang Normal University, Jinhua, Zhejiang 321004, China
Ding-Zhu Du: Department of Computer Science, University of Texas at Dallas, Richardson, Texas 75080
Zhao Zhang: School of Mathematical Sciences, Zhejiang Normal University, Jinhua, Zhejiang 321004, China

INFORMS Journal on Computing, 2024, vol. 36, issue 2, 510-525

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.

Keywords: approximation ratio; evolutionary algorithm; minimum weight general cover; minimum submodular cover; minimum connected dominating set (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.0327 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:36:y:2024:i:2:p:510-525

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().