University of Twente Student Theses
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.

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 realworld instances of problems. In this thesis we use random shortest path metrics applied to ErdősRényi random graphs. An ErdősRé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 kmedian problem all have a constant upper bound. Additionally, we show a polynomial upper bound for the expected number of iterations of the 2opt 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:  http://purl.utwente.nl/essays/75059 
Export this item as:  BibTeX EndNote HTML Citation Reference Manager 
Repository Staff Only: item control page