2022/10/03 by Yaoyao Zhang, Zhang, Yaoyao, Chaojie Zhu +9
Computer Science · Decision Sciences · Engineering · #68w15 #68w25 #Auction Theory and Applications #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #Neural and Evolutionary Computing (cs.NE) #Scheduling and Optimization Algorithms
paper · pdf · doi:10.48550/arxiv.2210.00672
openalex publication_date 2022/10/03 · openalex created_date 2022/10/06 · openalex updated_date 2026/07/28
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 generalized simple multi-objective evolutionary algorithm (GSEMO), and apply it on a minimum weight general cover problem. For a wide range of problems (including the 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 non-submodular), GSEMO yields asymptotically tight approximation ratios in expected polynomial time.