University of Twente Student Theses
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.
|
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: | https://purl.utwente.nl/essays/75651 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page