University of Twente Student Theses

Login

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

Hoogendijk, N. (2018) Smoothed analysis for partitioning algorithms for d-dimensional Euclidean optimization problems.

[img] PDF
299kB
Abstract: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).
Item Type:Essay (Bachelor)
Faculty:EEMCS: Electrical Engineering, Mathematics and Computer Science
Subject:31 mathematics
Programme:Applied Mathematics BSc (56965)
Link to this item:http://purl.utwente.nl/essays/75651
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page