### 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 language | English (US) |
---|---|

Title of host publication | Natural Computing Series |

Publisher | Springer |

Pages | 213-248 |

Number of pages | 36 |

DOIs | |

State | Published - Jan 1 2020 |

Externally published | Yes |

### Publication series

Name | Natural Computing Series |
---|---|

ISSN (Print) | 1619-7127 |

### Fingerprint

### Cite this

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

Research output: Chapter in Book/Report/Conference proceeding › Chapter

*Natural Computing Series.*Natural Computing Series, Springer, pp. 213-248. https://doi.org/10.1007/978-3-030-29414-4_4

}

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 -