A simple and deterministic competitive algorithm for online facility location

• DOI: 10.1016/j.ic.2004.06.002
• Publication Date: 2004-09-28T18:37:14Z
• Authors: Aris Anagnostopoulos; Russell Bent; Eli Upfal; Pascal Van Henten...
• Keywords: Competitive Analysis; Online algorithm; SIMPLE algorithm

AbstractThis 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(logn)-competitive under these various models, where n is the total number of customers. 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.