University of Twente Student Theses


Analysis of heuristics with random shortest path metrics on sparse graphs

Wackerle Garcia, L.M. (2020) Analysis of heuristics with random shortest path metrics on sparse graphs.

[img] PDF
Abstract:Classical optimisation problems can be impractical to solve to optimality for large instances. Simple heuristics have shown to perform strikingly well for such problems, producing near-optimal solutions with only a fraction of the time-complexity. Worst-case analysis of these heuristics suggests a far poorer performance than what we see in practice and so efforts to explain this behaviour have shifted to a probabilistic framework. Much analysis has already been done for heuristics on instances drawn from Euclidean space. While these instances have useful mathematical properties, they are not always representative of realistic networks. Recent efforts to shift the analysis to a more realistic distribution has seen results produced for random shortest path metrics generated from dense graphs and a small subset of sparse graphs. This thesis extends these findings to a wider class of sparse graphs by generalising recent results to sparse graphs with a fast growing cut size. The performance of three simple heuristics is analysed: the greedy heuristic for the minimum-distance perfect matching problem and the nearest neighbour and insertion heuristic for the travelling salesman problem. Applied within a probabilistic framework, it can be shown that all three heuristics achieve a constant expected approximation ratio.
Item Type:Essay (Bachelor)
Faculty:EEMCS: Electrical Engineering, Mathematics and Computer Science
Subject:31 mathematics, 54 computer science
Programme:Computer Science BSc (56964)
Link to this item:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page