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

DOI10.1145/3594805.3607134MaRDI QIDQ6120974zbMATH OpenOpenAlexWikidataFDO

Authors F. Neumann, Andrew M. Sutton

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

parameterized complexityruntime analysisvertex cover

Mathematics Subject Classification ID

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

Cites work

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

This page was built for publication: Fixed-Parameter Tractability of the (1 + 1) Evolutionary Algorithm on Random Planted Vertex Covers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6120974)