Smoothed Analysis of High-Dimensional Optimization Problems

[Master's thesis]

For many optimization problems, finding optimal solutions is prohibitive because the problems are NP-hard. This often holds even in the natural case, where the instances of the optimization problem consists of points in the Euclidean plane. In order to still be able to solve these problems, heuristics have been developed in order to find close-to-optimal in reasonable time. While many such heuristics show a remarkable performance in practice, their theoretical performance is poor and fails to explain practical observations.

Smoothed analysis is a relatively new paradigm in the analysis of algorithms that aims at explaining the performance of such heuristics for which there is a gap between theoretical analysis and practical observation.

Recently, Bläser et al. (Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals, Algorithmica, to appear) have developed a framework to analyze so-called partitioning heuristics for optimization problems embedded in the Euclidean plane. The goal of this thesis is to generalize this framework to higher dimensions and to apply it to analyze further heuristics for Euclidean optimization problems.

For more information, please contact Bodo Manthey.