Fixed-Parameter Tractability of the (1 + 1) Evolutionary Algorithm on Random Planted Vertex Covers

DOI10.1145/3594805.3607134OpenAlexW4385438147MaRDI QIDQ6120974

Andrew M. Sutton, Frank Neumann, Unnamed Author

Publication date: 23 February 2024

Published in: Proceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3594805.3607134

zbMATH Keywords

vertex coverparameterized complexityruntime analysis

Mathematics Subject Classification ID

Evolutionary algorithms, genetic algorithms (computational aspects) (68W50) Approximation methods and heuristics in mathematical programming (90C59) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Cites Work

• Unnamed Item
• Hiding cliques for cryptographic security
• Fixed-parameter evolutionary algorithms and the vertex cover problem
• First-hitting times under drift
• Time complexity analysis of evolutionary algorithms on random satisfiable \(k\)-CNF formulas
• Finding large cliques in sparse semi-random graphs by simple randomized search heuristics
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Large Cliques Elude the Metropolis Process
• Focused jump-and-repair constraint handling for fixed-parameter tractable graph problems
• Approximating vertex cover using edge-based representations
• Probability Inequalities for Sums of Bounded Random Variables
• Probability and Computing