## Abstract

The facility location problem is an NP-hard optimization problem. Therefore, approximation algorithms are often used to solve large instances. 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. However, 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 heuristic which gives a solution to the facility location problem: 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, this heuristic yields a 1+o(1) approximation in expectation. In the remaining few cases we show that this heuristic yields an O(1) approximation in expectation.

We investigate the facility location problem using random shortest path metrics. We analyze some probabilistic properties for a simple heuristic which gives a solution to the facility location problem: 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, this heuristic yields a 1+o(1) approximation in expectation. In the remaining few cases we show that this heuristic yields an O(1) approximation in expectation.

Original language | English |
---|---|

Pages | 97-100 |

Publication status | Published - Jun 2017 |

Event | 15th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2017 - Cologne, Germany Duration: 6 Jun 2017 → 8 Jun 2017 Conference number: 15 http://ctw.uni-koeln.de/ |

### Conference

Conference | 15th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2017 |
---|---|

Abbreviated title | CTW |

Country/Territory | Germany |

City | Cologne |

Period | 6/06/17 → 8/06/17 |

Internet address |

## Keywords

- Facility location
- Random shortest path
- random metric spaces
- Approximation Algorithm