Abstract
This chapter compiles a number of results that apply the theory of parameterized algorithmics to the running-time analysis of randomized search heuristics such as evolutionary algorithms. The parameterized approach articulates the running time of algorithms solving combinatorial problems in finer detail than traditional approaches from classical complexity theory. We outline the main results and proof techniques for a collection of randomized search heuristics tasked to solve NP-hard combinatorial optimization problems such as finding a minimum vertex cover in a graph, finding a maximum leaf spanning tree in a graph, and the traveling salesperson problem.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this chapter
Cite this chapter
Neumann, F., Sutton, A.M. (2020). Parameterized Complexity Analysis of Randomized Search Heuristics. In: Doerr, B., Neumann, F. (eds) Theory of Evolutionary Computation. Natural Computing Series. Springer, Cham. https://doi.org/10.1007/978-3-030-29414-4_4
Download citation
DOI: https://doi.org/10.1007/978-3-030-29414-4_4
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-29413-7
Online ISBN: 978-3-030-29414-4
eBook Packages: Computer ScienceComputer Science (R0)