Probabilistic Analysis of Facility Location on Random Shortest Path Metrics

Stefan Klootwijk*, Bodo Manthey

*Corresponding author for this work

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    4 Downloads (Pure)


    The facility location problem is an NP -hard optimization problem. Therefore, approximation algorithms are often used to solve large instances. Such algorithms often perform much better than worst-case analysis suggests. Therefore, probabilistic analysis is a widely used tool to analyze such algorithms. 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, and also instances with independent (random) edge lengths, which are non-metric, have been researched. We would like to extend this knowledge to other, more general, metrics. We investigate the facility location problem using random shortest path metrics. We analyze some probabilistic properties for a simple greedy heuristic which gives a solution to 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. On the other hand, for large values of κ, the analysis becomes more difficult, and we provide a closed-form expression as upper bound for the expected approximation ratio. In the special case where all facility opening costs are equal this closed-form expression reduces to O(ln(n)4) or O(1) or even 1 + o(1 ) if the opening costs are sufficiently small.

    Original languageEnglish
    Title of host publicationComputing with Foresight and Industry
    Subtitle of host publication15th Conference on Computability in Europe, CiE 2019, Durham, UK, July 15–19, 2019, Proceedings
    EditorsFlorin Manea, Barnaby Martin, Daniël Paulusma, Giuseppe Primiero
    Number of pages13
    ISBN (Electronic)978-3-030-22996-2
    ISBN (Print)978-3-030-22995-5
    Publication statusPublished - 19 Jun 2019
    Event15th Conference on Computability in Europe, CiE 2019 - Durham, United Kingdom
    Duration: 15 Jul 201919 Jul 2019
    Conference number: 15

    Publication series

    NameLecture Notes in Computer Science
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349


    Conference15th Conference on Computability in Europe, CiE 2019
    Abbreviated titleCiE 2019
    Country/TerritoryUnited Kingdom


    Dive into the research topics of 'Probabilistic Analysis of Facility Location on Random Shortest Path Metrics'. Together they form a unique fingerprint.

    Cite this