A Nearly Optimal Deterministic Online Algorithm for Non-Metric Facility Location
share
In the online non-metric variant of the facility location problem, there is a given graph consisting of set F of facilities (each with a certain opening cost), 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 the first online, polynomial-time deterministic algorithm for this problem, with competitive ratio of O(log |F| · (log |C| + loglog |F|)). The result is optimal up to loglog factors. Previously, the only known solution for this problem with a sub-linear competitive ratio was randomized [Alon et al., TALG 2006]. Our approach is based on solving a different fractional relaxation than that of Alon et al., where we combine dual fitting and multiplicative weight updates approaches. By maintaining certain monotonicity properties of the created fractional solution, we are able to handle the dependencies between facilities and connections in a rounding routine. Our result, combined with the algorithm by Naor et al. [FOCS 2011] implies the first deterministic algorithm for the online node-weighted Steiner tree problem. The resulting competitive ratio is O(log k ·log^2 ℓ) on graphs of ℓ nodes and k terminals.
READ FULL TEXT