Parameterized complexity analysis of randomized search heuristics
Date
2020
Authors
Neumann, F.
Sutton, A.M.
Editors
Doerr, B.
Neumann, F.
Neumann, F.
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Book chapter
Citation
Theory of Evolutionary Computation: Recent Developments in Discrete Optimization, 2020 / Doerr, B., Neumann, F. (ed./s), vol.abs/2001.05120, Ch.4, pp.213-248
Statement of Responsibility
Frank Neumann and Andrew M. Sutton
Conference Name
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.
School/Discipline
Dissertation Note
Provenance
Description
Access Status
Rights
© Springer Nature Switzerland AG 2020