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.STACS.2021.14
URN: urn:nbn:de:0030-drops-136598
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13659/
Bienkowski, Marcin ;
Feldkord, Björn ;
Schmidt, Paweł
A Nearly Optimal Deterministic Online Algorithm for Non-Metric Facility Location
Abstract
In the online non-metric variant of the facility location problem, there is a given graph consisting of a set F of facilities (each with a certain opening cost), a set C of potential clients, and weighted connections between them. The online part of the input is a sequence of clients from C, and in response to any requested client, an online algorithm may open an additional subset of facilities and must connect the given client to an open facility.
We give an online, polynomial-time deterministic algorithm for this problem, with a competitive ratio of O(log |F| ⋅ (log |C| + log log |F|)). The result is optimal up to loglog factors. Our algorithm improves over the O((log |C| + log |F|) ⋅ (log |C| + log log |F|))-competitive construction that first reduces the facility location instance to a set cover one and then later solves such instance using the deterministic algorithm by Alon et al. [TALG 2006]. This is an asymptotic improvement in a typical scenario where |F| ≪ |C|.
We achieve this by a more direct approach: we design an algorithm for a fractional relaxation of the non-metric facility location problem with clustered facilities. To handle the constraints of such non-covering LP, we combine the dual fitting and multiplicative weight updates approach. By maintaining certain additional monotonicity properties of the created fractional solution, we can handle the dependencies between facilities and connections in a rounding routine.
Our result, combined with the algorithm by Naor et al. [FOCS 2011] yields the first deterministic algorithm for the online node-weighted Steiner tree problem. The resulting competitive ratio is O(log k ⋅ log² ?) on graphs of ? nodes and k terminals.
BibTeX - Entry
@InProceedings{bienkowski_et_al:LIPIcs.STACS.2021.14,
author = {Bienkowski, Marcin and Feldkord, Bj\"{o}rn and Schmidt, Pawe{\l}},
title = {{A Nearly Optimal Deterministic Online Algorithm for Non-Metric Facility Location}},
booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
pages = {14:1--14:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-180-1},
ISSN = {1868-8969},
year = {2021},
volume = {187},
editor = {Bl\"{a}ser, Markus and Monmege, Benjamin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13659},
URN = {urn:nbn:de:0030-drops-136598},
doi = {10.4230/LIPIcs.STACS.2021.14},
annote = {Keywords: Online algorithms, deterministic rounding, linear programming, facility location, set cover}
}
|
Keywords: |
|
Online algorithms, deterministic rounding, linear programming, facility location, set cover |
|
Collection: |
|
38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
10.03.2021 |
