English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

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.

Probabilistic Analysis of Facility Location on Random Shortest Path Metrics