Abstract
Simple heuristics for combinatorial optimization problems often show a remarkable performance in practice. Worstcase analysis often falls short of explaining this performance. Because of this, ‘beyond worstcase analysis’ of algorithms has recently gained a lot of attention, including probabilistic analysis of algorithms.
The instances of many combinatorial optimization problems are essentially a discrete metric space. Probabilistic analysis for such metric optimization problems has nevertheless mostly been conducted on instances drawn from Euclidean space, which provides a structure that is usually heavily exploited in the analysis. However, most instances from practice are not Euclidean. Little work has been done on metric instances drawn from other, more realistic, distributions. Some initial results have been obtained by Bringmann et al. (Algorithmica, 2015), who have used random shortest path metrics generated from complete graphs to analyse heuristics.
In this thesis we look at several variations of the random shortest path metrics, and perform probabilistic analyses for some simple heuristics for several combinatorial optimization problems on these random metric spaces. A random shortest path metric is constructed by drawing independent random edge weights for each edge in a graph and setting the distance between every pair of vertices to the length of a shortest path between them, with respect to the drawn weights.
We provide some basic properties of the distances between vertices in random shortest path metrics. Using these properties, we perform several probabilistic analyses. For random shortest path metrics generated from (dense) ErdősRényi random graphs we show that the greedy heuristic for the minimumdistance perfect matching problem, the nearest neighbor and insertion heuristics for the traveling salesman problem, and a trivial heuristic for the kmedian problem all achieve a constant expected approximation ratio. Additionally, we show a polynomial upper bound for the expected number of iterations of the 2opt heuristic for the traveling salesman problem in this model.
For random shortest path metrics generated from sparse graphs we show that the greedy heuristic for the minimumdistance perfect matching problem, and the nearest neighbor and insertion heuristics for the traveling salesman problem all achieve a constant expected approximation ratio. Additionally, we show that the 2opt heuristic for the traveling salesman problem also achieves a constant expected approximation ratio in this model.
For random shortest path metrics generated from complete graphs we analyse a simple greedy heuristic for the facility location problem: opening the κ cheapest facilities (with κ only depending on the facility opening costs). If the facility opening costs are such that κ is not too large, then we show that this heuristic is asymptotically optimal. For large values of κ we provide a closedform expression as upper bound for the expected approximation ratio and we evaluate this expression for the special case where all facility opening costs are equal.
Moreover, we show in this model that a simple 2approximation algorithm for the Steiner tree problem is asymptotically optimal as long as the number of terminals is not too large. We also present some numerical results that imply that the 2opt heuristic for the traveling salesman problem seems to perform rather poorly in this model.
The instances of many combinatorial optimization problems are essentially a discrete metric space. Probabilistic analysis for such metric optimization problems has nevertheless mostly been conducted on instances drawn from Euclidean space, which provides a structure that is usually heavily exploited in the analysis. However, most instances from practice are not Euclidean. Little work has been done on metric instances drawn from other, more realistic, distributions. Some initial results have been obtained by Bringmann et al. (Algorithmica, 2015), who have used random shortest path metrics generated from complete graphs to analyse heuristics.
In this thesis we look at several variations of the random shortest path metrics, and perform probabilistic analyses for some simple heuristics for several combinatorial optimization problems on these random metric spaces. A random shortest path metric is constructed by drawing independent random edge weights for each edge in a graph and setting the distance between every pair of vertices to the length of a shortest path between them, with respect to the drawn weights.
We provide some basic properties of the distances between vertices in random shortest path metrics. Using these properties, we perform several probabilistic analyses. For random shortest path metrics generated from (dense) ErdősRényi random graphs we show that the greedy heuristic for the minimumdistance perfect matching problem, the nearest neighbor and insertion heuristics for the traveling salesman problem, and a trivial heuristic for the kmedian problem all achieve a constant expected approximation ratio. Additionally, we show a polynomial upper bound for the expected number of iterations of the 2opt heuristic for the traveling salesman problem in this model.
For random shortest path metrics generated from sparse graphs we show that the greedy heuristic for the minimumdistance perfect matching problem, and the nearest neighbor and insertion heuristics for the traveling salesman problem all achieve a constant expected approximation ratio. Additionally, we show that the 2opt heuristic for the traveling salesman problem also achieves a constant expected approximation ratio in this model.
For random shortest path metrics generated from complete graphs we analyse a simple greedy heuristic for the facility location problem: opening the κ cheapest facilities (with κ only depending on the facility opening costs). If the facility opening costs are such that κ is not too large, then we show that this heuristic is asymptotically optimal. For large values of κ we provide a closedform expression as upper bound for the expected approximation ratio and we evaluate this expression for the special case where all facility opening costs are equal.
Moreover, we show in this model that a simple 2approximation algorithm for the Steiner tree problem is asymptotically optimal as long as the number of terminals is not too large. We also present some numerical results that imply that the 2opt heuristic for the traveling salesman problem seems to perform rather poorly in this model.
Original language  English 

Qualification  Doctor of Philosophy 
Awarding Institution 

Supervisors/Advisors 

Thesis sponsors  
Award date  3 Nov 2021 
Place of Publication  Enschede 
Publisher  
Print ISBNs  9789036552493 
DOIs  
Publication status  Published  3 Nov 2021 
Fingerprint
Dive into the research topics of 'Probabilistic Analyses of Combinatorial Optimization Problems on Random Shortest Path Metrics'. Together they form a unique fingerprint.Datasets

FRaMeS_20220221_Numerical_Analysis_of_2OPT_for_TSP_on_RSPM
Klootwijk, S. (Creator), Areda (University of Twente), 21 Feb 2022
Dataset