On the approximation ability of evolutionary optimization with application to minimum set cover

DOI10.1016/j.artint.2012.01.001zbMath1238.68152arXiv1011.4028OpenAlexW2148311277MaRDI QIDQ420829

Zhi-Hua Zhou, Yang Yu, Xin Yao

Publication date: 23 May 2012

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1011.4028

zbMATH Keywords

approximation algorithmevolutionary algorithmsapproximation ratio\(k\)-set covertime complexity analysis

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation algorithms (68W25)

Related Items (7)

On the analysis of the (1+1) evolutionary algorithm for the maximum leaf spanning tree problem ⋮ Optimization methods for regularization-based ill-posed problems: a survey and a multi-objective framework ⋮ An analysis on recombination in multi-objective evolutionary optimization ⋮ Performance analysis of the \((1+1)\) evolutionary algorithm for the multiprocessor scheduling problem ⋮ Time complexity analysis of evolutionary algorithms for 2-hop \((1,2)\)-minimum spanning tree problem ⋮ Performance analysis of randomised search heuristics operating with a fixed budget ⋮ Optimizing group learning: an evolutionary computing approach

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Bioinspired computation in combinatorial optimization. Algorithms and their computational complexity
• Computing minimum cuts by randomized search heuristics
• Minimum spanning trees made easier via multi-objective optimization
• The analysis of evolutionary algorithms on sorting and shortest paths problems
• A new approach to estimating the expected first hitting time of evolutionary algorithms
• Algorithmic construction of sets for k -restrictions
• A threshold of ln n for approximating set cover
• Speeding up Approximation Algorithms for NP-Hard Spanning Forest Problems by Multi-objective Optimization
• A Greedy Heuristic for the Set-Covering Problem
• A Tight Analysis of the Greedy Algorithm for Set Cover
• Approximating the Unweighted ${k}$-Set Cover Problem: Greedy Meets Local Search
• Greedy in Approximation Algorithms
• A Better-Than-Greedy Approximation Algorithm for the Minimum Set Cover Problem
• STACS 2005
• Drift analysis and average time complexity of evolutionary algorithms

This page was built for publication: On the approximation ability of evolutionary optimization with application to minimum set cover