License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2018.21
URN: urn:nbn:de:0030-drops-94843
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9484/
Cygan, Marek ;
Czumaj, Artur ;
Mucha, Marcin ;
Sankowski, Piotr
Online Facility Location with Deletions
Abstract
In this paper we study three previously unstudied variants of the online Facility Location problem, considering an intrinsic scenario when the clients and facilities are not only allowed to arrive to the system, but they can also depart at any moment.
We begin with the study of a natural fully-dynamic online uncapacitated model where clients can be both added and removed. When a client arrives, then it has to be assigned either to an existing facility or to a new facility opened at the client's location. However, when a client who has been also one of the open facilities is to be removed, then our model has to allow to reconnect all clients that have been connected to that removed facility. In this model, we present an optimal O(log(n_{act}) / log log(n_{act}))-competitive algorithm, where n_{act} is the number of active clients at the end of the input sequence.
Next, we turn our attention to the capacitated Facility Location problem. We first note that if no deletions are allowed, then one can achieve an optimal competitive ratio of O(log(n) / log(log n)), where n is the length of the sequence. However, when deletions are allowed, the capacitated version of the problem is significantly more challenging than the uncapacitated one. We show that still, using a more sophisticated algorithmic approach, one can obtain an online O(log N + log c log n)-competitive algorithm for the capacitated Facility Location problem in the fully dynamic model, where N is number of points in the input metric and c is the capacity of any open facility.
BibTeX - Entry
@InProceedings{cygan_et_al:LIPIcs:2018:9484,
author = {Marek Cygan and Artur Czumaj and Marcin Mucha and Piotr Sankowski},
title = {{Online Facility Location with Deletions}},
booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)},
pages = {21:1--21:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-081-1},
ISSN = {1868-8969},
year = {2018},
volume = {112},
editor = {Yossi Azar and Hannah Bast and Grzegorz Herman},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9484},
URN = {urn:nbn:de:0030-drops-94843},
doi = {10.4230/LIPIcs.ESA.2018.21},
annote = {Keywords: online algorithms, facility location, fully-dynamic online algorithms}
}
|
Keywords: |
|
online algorithms, facility location, fully-dynamic online algorithms |
|
Collection: |
|
26th Annual European Symposium on Algorithms (ESA 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
14.08.2018 |
