Strategic online facility location

Maximilian Drees, Björn Feldkord, Alexander Skopalik

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

2 Citations (Scopus)

Abstract

In this paper we consider a strategic variant of the online facility location problem. Given is a graph in which each node serves two roles: it is a strategic client stating requests as well as a potential location for a facility. In each time step one client states a request which induces private costs equal to the distance to the closest facility. Before serving, the clients may collectively decide to open new facilities, sharing the corresponding price. Instead of optimizing the global costs, each client acts selfishly. The prices of new facilities vary between nodes and also change over time, but are always bounded by some fixed value α . Both the requests as well as the facility prices are given by an online sequence and are not known in advance.

We characterize the optimal strategies of the clients and analyze their overall performance in comparison to a centralized offline solution. If all players optimize their own competitiveness, the global performance of the system is O(α−−√⋅α) times worse than the offline optimum. A restriction to a natural subclass of strategies improves this result to O(α) . We also show that for fixed facility costs, we can find strategies such that this bound further improves to O(α−−√) .
Original languageEnglish
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
EditorsT-H. Hubert Chan, Minming Li, Lusheng Wang
PublisherSpringer
Pages593-607
Number of pages15
ISBN (Electronic)978-3-319-48749-6
ISBN (Print)978-3-319-48748-9
DOIs
Publication statusPublished - 2016
Externally publishedYes
Event10th International Conference on Combinatorial Optimization and Applications 2016 - Hong Kong, China
Duration: 16 Dec 201618 Dec 2016
Conference number: 10
https://conference.cs.cityu.edu.hk/cocoa2016/

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10043 LNCS

Conference

Conference10th International Conference on Combinatorial Optimization and Applications 2016
Abbreviated titleCOCOA 2016
CountryChina
CityHong Kong
Period16/12/1618/12/16
Internet address

Keywords

  • Algorithmic game theory
  • Competitive analysis
  • Facility location
  • Online algorithms

Fingerprint Dive into the research topics of 'Strategic online facility location'. Together they form a unique fingerprint.

Cite this