The main aim of randomized search heuristics is to produce good approximations of optimal solutions within a small amount of time. In contrast to numerous experimental results, there are only a few theoretical results on this subject. We consider the approximation ability of randomized search for the class of covering ... more >>>

Ant Colony Optimization (ACO) is a kind of randomized search heuristic that has become very popular for solving problems from combinatorial optimization. Solutions for a given problem are constructed by a random walk on a so-called construction graph. This random walk can be influenced by heuristic information about the problem. ... more >>>

Ant Colony Optimization (ACO) has become quite popular in recent years. In contrast to many successful applications, the theoretical foundation of this randomized search heuristic is rather weak. Building up such a theory is demanded to understand how these heuristics work as well as to come up with better algorithms ... more >>>

We investigate the effect of restricting the mutation operator in evolutionary algorithms with respect to the runtime behavior. Considering the Eulerian cycle problem we present runtime bounds on evolutionary algorithms with a restricted operator that are much smaller than the best upper bounds for the general case. In our analysis ... more >>>

We give faster approximation algorithms for the generalization of two NP-hard spanning tree problems. First, we investigate the problem of minimizing the degree of minimum spanning forests. The task is to compute for each number of connected components a minimum spanning forest whose degree is as small as possible. Fischer ... more >>>