Probabilistic analysis of facility location on random shortest path metrics

DOI10.1007/978-3-030-22996-2_4zbMATH Open1439.90049arXiv1903.11980OpenAlexW2544285781MaRDI QIDQ2179347FDOQ2179347

Authors: Stefan Klootwijk, Bodo Manthey 

Publication date: 12 May 2020

Abstract: 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 $kappa$ cheapest facilities (with $kappa$ only depending on the facility opening costs). If the facility opening costs are such that $kappa$ is not too large, then we show that this heuristic is asymptotically optimal. On the other hand, for large values of $kappa$, 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(sqrt[4]ln(n))$ or $O(1)$ or even $1+o(1)$ if the opening costs are sufficiently small.

Full work available at URL: https://arxiv.org/abs/1903.11980

Recommendations

• On the Average Case Performance of Some Greedy Approximation Algorithms For the Uncapacitated Facility Location Problem
• scientific article; zbMATH DE number 1303535
• Analysis of a Local Search Heuristic for Facility Location Problems

zbMATH Keywords

facility locationrandom shortest path metrics

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Discrete location and assignment (90B80)

This page was built for publication: Probabilistic analysis of facility location on random shortest path metrics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2179347)