Parameterized complexity analysis of randomized search heuristics

Frank Neumann, Andrew M. Sutton

Research output: Chapter in Book/Report/Conference proceedingChapter

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.

Original languageEnglish (US)
Title of host publicationNatural Computing Series
PublisherSpringer
Pages213-248
Number of pages36
DOIs
StatePublished - Jan 1 2020
Externally publishedYes

Publication series

NameNatural Computing Series
ISSN (Print)1619-7127

Fingerprint

Parameterized Complexity
Complexity Analysis
Heuristic Search
Combinatorial optimization
Evolutionary algorithms
Complexity Theory
Vertex Cover
Combinatorial Problems
Graph in graph theory
Combinatorial Optimization Problem
Spanning tree
Evolutionary Algorithms
Leaves
NP-complete problem

Cite this

Neumann, F., & Sutton, A. M. (2020). Parameterized complexity analysis of randomized search heuristics. In Natural Computing Series (pp. 213-248). (Natural Computing Series). Springer. https://doi.org/10.1007/978-3-030-29414-4_4

Parameterized complexity analysis of randomized search heuristics. / Neumann, Frank; Sutton, Andrew M.

Natural Computing Series. Springer, 2020. p. 213-248 (Natural Computing Series).

Research output: Chapter in Book/Report/Conference proceedingChapter

Neumann, F & Sutton, AM 2020, Parameterized complexity analysis of randomized search heuristics. in Natural Computing Series. Natural Computing Series, Springer, pp. 213-248. https://doi.org/10.1007/978-3-030-29414-4_4
Neumann F, Sutton AM. Parameterized complexity analysis of randomized search heuristics. In Natural Computing Series. Springer. 2020. p. 213-248. (Natural Computing Series). https://doi.org/10.1007/978-3-030-29414-4_4
Neumann, Frank ; Sutton, Andrew M. / Parameterized complexity analysis of randomized search heuristics. Natural Computing Series. Springer, 2020. pp. 213-248 (Natural Computing Series).
@inbook{e2f62f0a5510440caa64bdc8b4e2b5f0,
title = "Parameterized complexity analysis of randomized search heuristics",
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.",
author = "Frank Neumann and Sutton, {Andrew M.}",
year = "2020",
month = "1",
day = "1",
doi = "10.1007/978-3-030-29414-4_4",
language = "English (US)",
series = "Natural Computing Series",
publisher = "Springer",
pages = "213--248",
booktitle = "Natural Computing Series",

}

TY - CHAP

T1 - Parameterized complexity analysis of randomized search heuristics

AU - Neumann, Frank

AU - Sutton, Andrew M.

PY - 2020/1/1

Y1 - 2020/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85076120866&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85076120866&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-29414-4_4

DO - 10.1007/978-3-030-29414-4_4

M3 - Chapter

AN - SCOPUS:85076120866

T3 - Natural Computing Series

SP - 213

EP - 248

BT - Natural Computing Series

PB - Springer

ER -