On the competitive ratio for online facility location

We consider the problem of Online Facility Location, where the demand points arrive online and must be assigned irrevocably to an open facility upon arrival. The objective is to minimize the sum of facility and assignment costs. We prove that the competitive ratio for Online Facility Location is Θ(log n/log log n). On the negative side, we show that no randomized algorithm can achieve a competitive ratio better than Ω(log n/log log n) against an oblivious adversary, even if the demands lie on a line segment. On the positive side, we present a deterministic algorithm which achieves a competitive ratio of O(log n/log log n) in every metric space.