Superpolynomial lower bounds for the \((1+1)\) EA on some easy combinatorial problems

DOI10.1007/s00453-015-0027-5zbMath1360.68791OpenAlexW2468335684MaRDI QIDQ306491

Andrew M. Sutton

Publication date: 31 August 2016

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-015-0027-5

zbMATH Keywords

lower boundstime complexityevolutionary algorithmruntime analysis(1 + 1) EA

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Symmetry breaking for voting mechanisms ⋮ Artificial immune systems can find arbitrarily good approximations for the NP-hard number partitioning problem

Cites Work

• Bioinspired computation in combinatorial optimization. Algorithms and their computational complexity
• Computing minimum cuts by randomized search heuristics
• Simplified drift analysis for proving lower bounds in evolutionary computation
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Multiplicative drift analysis
• Upper and lower bounds for randomized search heuristics in black-box optimization
• The one-dimensional Ising model: mutation versus recombination
• Probability with Martingales
• A Random Recolouring Method for Graphs and Hypergraphs
• Tight Bounds on the Optimization Time of a Randomized Search Heuristic on Linear Functions
• The complexity of satisfiability problems
• Generalization of a Probability Limit Theorem of Cramer
• Unnamed Item
• Unnamed Item
• Unnamed Item