The Library
Online facility location with deletions
Tools
Cygan, Marek, Czumaj, Artur, Mucha, Marcin and Sankowski, Piotr (2018) Online facility location with deletions. In: 26th Annual European Symposium on Algorithms (ESA 2018), Helsinki, Finland, 20-24 Aug 2018. Published in: {26th Annual European Symposium on Algorithms (ESA 2018), 112 21:1-21:15. ISBN 9783959770811. doi:10.4230/LIPIcs.ESA.2018.21 ISSN 1868-8969.
|
PDF
WRAP-online-facility-location-deletions-Czumaj-2018.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (486Kb) | Preview |
Official URL: https://doi.org/10.4230/LIPIcs.ESA.2018.21
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/ log log N)-competitive algorithm, where N 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 m+log c log n)-competitive algorithm for the capacitated Facility Location problem in the fully dynamic model, where m is number of points in the input metric and c is the capacity of any open facility.
Item Type: | Conference Item (Paper) | |||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | |||||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||||||||
Library of Congress Subject Headings (LCSH): | Online algorithms, Combinatorial optimization | |||||||||||||||
Series Name: | Leibniz International Proceedings in Informatics (LIPIcs) | |||||||||||||||
Journal or Publication Title: | {26th Annual European Symposium on Algorithms (ESA 2018) | |||||||||||||||
Publisher: | Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik | |||||||||||||||
ISBN: | 9783959770811 | |||||||||||||||
ISSN: | 1868-8969 | |||||||||||||||
Official Date: | 18 June 2018 | |||||||||||||||
Dates: |
|
|||||||||||||||
Volume: | 112 | |||||||||||||||
Page Range: | 21:1-21:15 | |||||||||||||||
DOI: | 10.4230/LIPIcs.ESA.2018.21 | |||||||||||||||
Status: | Peer Reviewed | |||||||||||||||
Publication Status: | Published | |||||||||||||||
Access rights to Published version: | Open Access (Creative Commons) | |||||||||||||||
Date of first compliant deposit: | 17 August 2018 | |||||||||||||||
Date of first compliant Open Access: | 17 August 2018 | |||||||||||||||
Funder: | Royal Society (Great Britain) | |||||||||||||||
RIOXX Funder/Project Grant: |
|
|||||||||||||||
Conference Paper Type: | Paper | |||||||||||||||
Title of Event: | 26th Annual European Symposium on Algorithms (ESA 2018) | |||||||||||||||
Type of Event: | Conference | |||||||||||||||
Location of Event: | Helsinki, Finland | |||||||||||||||
Date(s) of Event: | 20-24 Aug 2018 | |||||||||||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year