Online facility location

TLDR

The study provides a randomized online O(1)-competitive algorithm for facility location when points arrive in random order. The algorithms are randomized, rely on expected waiting time analysis, and incorporate Charikar and Guha’s techniques to achieve a linear‑time constant approximation for offline facility location. For adversarial ordering, no constant‑competitive algorithm exists, but an O(log n)-competitive algorithm is achieved, and the combined approach yields a linear‑time constant approximation for offline facility location.

Abstract

We consider the online variant of facility location, in which demand points arrive one at a time and we must maintain a set of facilities to service these points. We provide a randomized online O(1)-competitive algorithm in the case where points arrive in random order. If points are ordered adversarially, we show that no algorithm can be constant-competitive, and provide an O(log n)-competitive algorithm. Our algorithms are randomized and the analysis depends heavily on the concept of expected waiting time. We also combine our techniques with those of M. Charikar and S. Guha (1999) to provide a linear-time constant approximation for the offline facility location problem.