University of Twente Student Theses

Login

Probabilistic analysis of optimization problems in random shortest path metrics applied to Erdős–Rényi random graphs

Visser, S.K. (2018) Probabilistic analysis of optimization problems in random shortest path metrics applied to Erdős–Rényi random graphs.

[img] PDF
1MB
Abstract:Probabilistic analysis for metric optimization problems has mostly been conducted on instances from the Euclidean space. Little analysis has been done on metric instances drawn from other distributions. We want to extend the probabilistic analysis of optimization problems to more general metrics, since these might provide a better resemblance to real-world instances of problems. In this thesis we use random shortest path metrics applied to Erdős-Rényi random graphs. An Erdős-Rényi random graph is constructed by including an edge between every pair of vertices independently with probability p. A random shortest path metric is then constructed by drawing independent random edge weights for each edge and setting the distance between every pair of vertices to the length of a shortest path between them with respect to the drawn weights. For these metrics, we prove that the expected approximation ratios of the greedy heuristic for the minimum distance maximum matching problem, of the nearest neighbor and insertion heuristics for the traveling salesman problem, and of the trivial heuristic for the k-median problem all have a constant upper bound. Additionally, we show a polynomial upper bound for the expected number of iterations of the 2-opt heuristic for the traveling salesman problem.
Item Type:Essay (Master)
Faculty:EEMCS: Electrical Engineering, Mathematics and Computer Science
Subject:31 mathematics
Programme:Applied Mathematics MSc (60348)
Link to this item:https://purl.utwente.nl/essays/75059
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page