## 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 κ 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 language | English |
---|---|

Title of host publication | Computing with Foresight and Industry |

Subtitle of host publication | 15th Conference on Computability in Europe, CiE 2019, Durham, UK, July 15–19, 2019, Proceedings |

Editors | Florin Manea, Barnaby Martin, Daniël Paulusma, Giuseppe Primiero |

Publisher | Springer Verlag |

Pages | 37-49 |

Number of pages | 13 |

ISBN (Electronic) | 978-3-030-22996-2 |

ISBN (Print) | 978-3-030-22995-5 |

DOIs | |

Publication status | Published - 19 Jun 2019 |

Event | 15th Conference on Computability in Europe, CiE 2019 - Durham, United Kingdom Duration: 15 Jul 2019 → 19 Jul 2019 Conference number: 15 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer |

Volume | 11558 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 15th Conference on Computability in Europe, CiE 2019 |
---|---|

Abbreviated title | CiE 2019 |

Country | United Kingdom |

City | Durham |

Period | 15/07/19 → 19/07/19 |