2019/03/28 by Stefan Klootwijk, Klootwijk, Stefan, Bodo Manthey +1 · 1 citation
Business, Management and Accounting · Computer Science · #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Facility Location and Emergency Management #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.1903.11980
openalex publication_date 2019/03/28 · openalex created_date 2022/07/12 · openalex updated_date 2026/07/28
The facility location problem is an NP-hard optimization problem. Therefore,\napproximation algorithms are often used to solve large instances. Such\nalgorithms often perform much better than worst-case analysis suggests.\nTherefore, probabilistic analysis is a widely used tool to analyze such\nalgorithms. Most research on probabilistic analysis of NP-hard optimization\nproblems involving metric spaces, such as the facility location problem, has\nbeen focused on Euclidean instances, and also instances with independent\n(random) edge lengths, which are non-metric, have been researched. We would\nlike to extend this knowledge to other, more general, metrics.\n We investigate the facility location problem using random shortest path\nmetrics. We analyze some probabilistic properties for a simple greedy heuristic\nwhich gives a solution to the facility location problem: opening the \κ\ncheapest facilities (with \κ only depending on the facility opening\ncosts). If the facility opening costs are such that \κ is not too large,\nthen we show that this heuristic is asymptotically optimal. On the other hand,\nfor large values of \κ, the analysis becomes more difficult, and we\nprovide a closed-form expression as upper bound for the expected approximation\nratio. In the special case where all facility opening costs are equal this\nclosed-form expression reduces to O(\√[4]\ln(n)) or O(1) or even\n1+o(1) if the opening costs are sufficiently small.\n