Title: Parameterized Complexity Analysis of Randomized Search Heuristics for
NP-hard Problems

Abstract:

One way of tackling NP-hard problems is by using some kind of
*heuristic* approach that might perform well on a reasonable subset of
instances. However, it isn't always clear for which instances such an
approach will succeed. In the real world, problem inputs are often
structured or restricted in some way that can be exploited by
heuristics. Classical worst-case analysis is not always well-suited for
these algorithms on real-world problems because it does not take such
structure into account. Parameterized complexity theory is a framework
that relates this structure to the running time of an algorithm by
considering extra parameters in addition to the input size of the problem.

In this talk I will discuss the application of parameterized complexity
theory to a class of algorithmic procedures called *randomized search
heuristics*. Randomized search heuristics (e.g., stochastic local
search, evolutionary algorithms, simulated annealing, ant colony
optimization) are often cited as "general purpose" algorithms because
they are typically easy to deploy and often do not require deep
domain-specific knowledge. I will argue that parameterized analysis
makes especially good sense for these algorithms, and present some
recent parameterized results.