### Combinatorial Optimization and the Analysis of Randomized Search Heuristics

Abstract

Randomized search heuristics have widely been applied to complex engineering problems
as well as to problems from combinatorial optimization. We investigate the runtime behavior
of randomized search heuristics and present runtime bounds for these heuristics
on some well-known combinatorial optimization problems. Such analyses can help to understand
better the working principle of these algorithms on combinatorial optimization
problems as well as help to design better algorithms for a newly given problem. Our analyses
mainly consider evolutionary algorithms that have achieved good results on a wide
class of NP-hard combinatorial optimization problems. We start by analyzing some easy
single-objective optimization problems such as the minimum spanning tree problem or the
problem of computing an Eulerian cycle of a given Eulerian graph and prove bounds on
the runtime of simple evolutionary algorithms. For the minimum spanning tree problem
we also investigate a multi-objective model and show that randomized search heuristics
find minimum spanning trees easier in this model than in a single-objective one. Many
polynomial solvable problems become NP-hard when a second objective has to be optimized
at the same time. We show that evolutionary algorithms are able to compute good
approximations for such problems by examining the NP-hard multi-objective minimum
spanning tree problem. Another kind of randomized search heuristic is ant colony optimization.
Up to now no runtime bounds have been achieved for this kind of heuristic. We
investigate a simple ant colony optimization algorithm and present a first runtime analysis.
At the end we turn to classical approximation algorithms. Motivated by our investigations
of randomized search heurisitics for the minimum spanning tree problem, we present a
multi-objective model for NP-hard spanning tree problems and show that the model can
help to speed up approximation algorithms for this kind of problems.