On the approximation ability of evolutionary optimization with application to minimum set cover
From MaRDI portal
Publication:420829
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
approximation algorithmevolutionary algorithmsapproximation ratio\(k\)-set covertime complexity analysis
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
