Parameterized Complexity Analysis of Randomized Search Heuristics
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Combinatorial OptimizationEvolutionary AlgorithmsSimilar Papers 제목 키워드 기반
Probabilistic Tools for the Analysis of Randomized Optimization Heuristics
This chapter collects several probabilistic tools that proved to be useful in the analysis of randomized search heuristics. This includes classic material like Markov, Chebyshev and Chernoff inequalities, but also lesser…
Time Complexity Analysis of Randomized Search Heuristics for the Dynamic Graph Coloring Problem
We contribute to the theoretical understanding of randomized search heuristics for dynamic problems. We consider the classical vertex coloring problem on graphs and investigate the dynamic setting where edges are added t…
Parameterized Complexity Results for Plan Reuse
Planning is a notoriously difficult computational problem of high worst-case complexity. Researchers have been investing significant efforts to develop heuristics or restrictions to make planning practically feasible. Ca…
Error Analysis of Elitist Randomized Search Heuristics
When globally optimal solutions of complicated optimization problems cannot be located by evolutionary algorithms (EAs) in polynomial expected running time, the hitting time/running time analysis is not flexible enough t…
Evolutionary AlgorithmsExploring Viable Algorithmic Options for Learning from Demonstration (LfD): A Parameterized Complexity Approach
The key to reconciling the polynomial-time intractability of many machine learning tasks in the worst case with the surprising solvability of these tasks by heuristic algorithms in practice seems to be exploiting restric…