Research output per year
Research output per year
Stefan Klootwijk, Bodo Manthey
Research output: Contribution to conference › Abstract › Academic
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.
Original language | English |
---|---|
Pages | 97-100 |
Number of pages | 4 |
Publication status | Published - 2020 |
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 | 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 |
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review