Smoothed analysis for partitioning algorithms for d-dimensional Euclidean optimization problems

Bl¨aser, Manthey and Rao [2], developed a framework for smoothed analysis of partitioning heuristics for 2-dimensional Euclidean optimization problems. In this paper, we will generalize this framework, so it can be applied on higher 1 dimensions. We will mostly follow the outline of Bl¨aser, Manthey and Rao’s article [2], with certain definitions and theorems changed where needed. We develop a model where the adversary specifies n density functions f1, ..., fn : [0, 1]d → [0, φ], one for each point. Then we draw xi independently to their corresponding density function to get the actual point set. φ lets us control the adversary’s power, the larger φ, the more powerful the adversary becomes. After we have developed the framework, we will apply it to certain partitioning algorithms for Euclidean Minimum Matching (Sect. 4), Euclidean Steiner trees (Sect. 5), Euclidean traveling salesman problem (Sect. 6) and Euclidean degree-bounded minimum-spanning tree (Sect. 7).