×

On the competitive ratio for online facility location. (English) Zbl 1039.68117

Baeten, Jos C. M. (ed.) et al., Automata, languages and programming. 30th international colloquium, ICALP 2003, Eindhoven, The Netherland, June 30 – July 4, 2003. Proceedings. Berlin: Springer (ISBN 3-540-40493-7/pbk). Lect. Notes Comput. Sci. 2719, 637-652 (2003).
Summary: We consider the problem of Online Facility Location, where demands arrive online and must be irrevocably assigned 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 \(\Theta({\frac{\log n}{\log\log n}})\). On the negative side, we show that no randomized algorithm can achieve a competitive ratio better than \(\Omega({\frac{\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 achieving a competitive ratio of O\(({\frac{\log n}{\log\log n}})\). The analysis is based on a hierarchical decomposition of the optimal facility locations such that each component either is relatively well-separated or has a relatively large diameter, and a potential function argument which distinguishes between the two kinds of components.
For the entire collection see [Zbl 1029.00041].

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90B80 Discrete location and assignment
PDFBibTeX XMLCite
Full Text: Link