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

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

We systematically study the hardness and the approximability of combinatorial multi-objective NP optimization problems (multi-objective problems, for short).

We define solution notions that precisely capture the typical algorithmic tasks in multi-objective optimization. These notions inherit polynomial-time Turing reducibility from multivalued functions, which allows us to compare the solution notions and ... more >>>