Probabilistic Analysis of Facility Location on Random Shortest Path Metrics

Research output: Contribution to conferenceAbstractOther research output

56 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
Publication statusPublished - Jun 2017
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
CountryGermany
CityCologne
Period6/06/178/06/17
Internet address

Keywords

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

Fingerprint Dive into the research topics of 'Probabilistic Analysis of Facility Location on Random Shortest Path Metrics'. Together they form a unique fingerprint.

Cite this