Tech Report CS-03-16

A Simple and Deterministic Competitive\\ Algorithm for Online Facility Location

Aris Anagnostopoulos, Russell Bent,\\ Eli Upfal, and Pascal Van Hentenryck

September 2003

Abstract:

This paper presents a deterministic and efficient algorithm for online facility location. The algorithm is based on a simple hierarchical partitioning and is extremely simple to implement. It also applies to a variety of models, i.e., models where the facilities can be placed anywhere in the region, or only at customer sites, or only at fixed locations. The paper shows that the algorithm is O(log n)-competitive under these various models. It also shows that the algorithm is O(1)-competitive with high probability and for any arrival order when customers are uniformly distributed or when they follow a distribution satisfying a smoothness property. Experimental results for a variety of scenarios indicate that the algorithm behaves extremely well in practice.

(complete text in pdf or gzipped postscript)