Probabilistic Analysis of Facility Location on Random Shortest Path Metrics

Klootwijk, S. (2016) Probabilistic Analysis of Facility Location on Random Shortest Path Metrics.

Abstract:The facility location problem is an NP-hard optimization problem. Therefore, approximation algorithms are often used to solve large instances. In practical situations, these approximation algorithms perform better than their worst-case approximation ratios suggest. In order to explain this behavior, probabilistic analysis is a widely used tool. Most research on probabilistic analysis of NP-hard optimization problems involving metric spaces, such as the facility location problem, has been focused on Euclidean instances. However, we would like to extend this knowledge to other, more general, metrics, since these provide a better resemblance to real-world instances. In this thesis we investigate the facility location problem using random shortest path metrics. A random shortest path metric is constructed by drawing independent random edge weights for each edge in a complete graph and then setting the distance between each pair of vertices to the length of a shortest path between them (according to the drawn edge weights). We analyze some probabilistic properties for three simple procedures which give a solution to the facility location problem: opening all facilities, opening one arbitrary facility, and opening a certain number of arbitrary facilities (with that certain number only depending on the facility opening cost). We show that, for almost any facility opening cost, at least one of these three procedures yields a 1+o(1) approximation in expectation. In the latter case we show that at least one of the three procedures yields an O(1) approximation in expectation.
Item Type:Essay (Master)
Faculty:EEMCS: Electrical Engineering, Mathematics and Computer Science
Subject:31 mathematics
Programme:Applied Mathematics MSc (60348)
Link to this item:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page