License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.45
URN: urn:nbn:de:0030-drops-171678
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17167/
Bienkowski, Marcin ;
Böhm, Martin ;
Byrka, Jarosław ;
Marcinkowski, Jan
Online Facility Location with Linear Delay
Abstract
In the problem of online facility location with delay, a sequence of n clients appear in the metric space, and they need to be eventually connected to some open facility. The clients do not have to be connected immediately, but such a choice comes with a certain penalty: each client incurs a waiting cost (equal to the difference between its arrival and its connection time). At any point in time, an algorithm may decide to open a facility and connect any subset of clients to it. That is, an algorithm needs to balance three types of costs: cost of opening facilities, costs of connecting clients, and the waiting costs of clients. We study a natural variant of this problem, where clients may be connected also to an already open facility, but such action incurs an extra cost: an algorithm pays for waiting of the facility (a cost incurred separately for each such "late" connection). This is reminiscent of online matching with delays, where both sides of the connection incur a waiting cost. We call this variant two-sided delay to differentiate it from the previously studied one-sided delay, where clients may connect to a facility only at its opening time.
We present an O(1)-competitive deterministic algorithm for the two-sided delay variant. Our approach is an extension of the approach used by Jain, Mahdian and Saberi [STOC 2002] for analyzing the performance of offline algorithms for facility location. To this end, we substantially simplify the part of the original argument in which a bound on the sequence of factor-revealing LPs is derived. We then show how to transform our O(1)-competitive algorithm for the two-sided delay variant to O(log n / log log n)-competitive deterministic algorithm for one-sided delays. This improves the known O(log n) bound by Azar and Touitou [FOCS 2020]. We note that all previous online algorithms for problems with delays in general metrics have at least logarithmic ratios.
BibTeX - Entry
@InProceedings{bienkowski_et_al:LIPIcs.APPROX/RANDOM.2022.45,
author = {Bienkowski, Marcin and B\"{o}hm, Martin and Byrka, Jaros{\l}aw and Marcinkowski, Jan},
title = {{Online Facility Location with Linear Delay}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
pages = {45:1--45:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-249-5},
ISSN = {1868-8969},
year = {2022},
volume = {245},
editor = {Chakrabarti, Amit and Swamy, Chaitanya},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17167},
URN = {urn:nbn:de:0030-drops-171678},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.45},
annote = {Keywords: online facility location, network design problems, facility location with delay, JMS algorithm, competitive analysis, factor revealing LP}
}
|
Keywords: |
|
online facility location, network design problems, facility location with delay, JMS algorithm, competitive analysis, factor revealing LP |
|
Collection: |
|
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
15.09.2022 |
|
Supplementary Material: |
|
Software: https://github.com/bohm/fl-double-sided-waiting |
