12 października 2021 10:15
[Seminarium ZOK] Marcin Bieńkowski: "A Nearly Optimal Deterministic Online Algorithm for Non-Metric Facility Location"
Streszczenie:
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. To this end, 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.
Joint work with Björn Feldkord and Paweł Schmidt.