Probabilistic analysis of facility location on random shortest path metrics

Stefan Klootwijk, Bodo Manthey

Research output: Contribution to conferenceAbstractAcademic

145 Downloads (Pure)

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.

Original languageEnglish
Pages97-100
Number of pages4
Publication statusPublished - 2020
Event15th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2017 - Cologne, Germany
Duration: 6 Jun 20178 Jun 2017
Conference number: 15
http://ctw.uni-koeln.de/

Conference

Conference15th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2017
Abbreviated titleCTW
Country/TerritoryGermany
CityCologne
Period6/06/178/06/17
Internet address

Keywords

  • Approximation algorithm
  • Facility location
  • Random metrics
  • Random shortest paths

Fingerprint

Dive into the research topics of 'Probabilistic analysis of facility location on random shortest path metrics'. Together they form a unique fingerprint.
  • Probabilistic Analysis of Facility Location on Random Shortest Path Metrics

    Klootwijk, S. & Manthey, B., 19 Jun 2019, Computing with Foresight and Industry: 15th Conference on Computability in Europe, CiE 2019, Durham, UK, July 15–19, 2019, Proceedings. Manea, F., Martin, B., Paulusma, D. & Primiero, G. (eds.). Springer, p. 37-49 13 p. (Lecture Notes in Computer Science; vol. 11558).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    4 Downloads (Pure)

Cite this