Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/132164
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Book chapter |
Title: | Parameterized complexity analysis of randomized search heuristics |
Author: | Neumann, F. Sutton, A.M. |
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 |
Publisher: | Springer |
Publisher Place: | Cham; Switzerland |
Issue Date: | 2020 |
Series/Report no.: | Natural Computing Series |
ISBN: | 3030294137 9783030294137 |
Editor: | Doerr, B. Neumann, F. |
Statement of Responsibility: | Frank Neumann and Andrew M. Sutton |
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. |
Rights: | © Springer Nature Switzerland AG 2020 |
DOI: | 10.1007/978-3-030-29414-4_4 |
Published version: | https://link.springer.com/book/10.1007/978-3-030-29414-4 |
Appears in Collections: | Aurora harvest Computer Science publications |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.