On the Competitive Ratio for Online Facility Location |
| |
Authors: | Dimitris Fotakis |
| |
Affiliation: | (1) Department of Information and Communication Systems Engineering, University of the Aegean, 83200 Karlovasi, Samos, Greece |
| |
Abstract: | 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 Θ . On the negative side, we show that no randomized algorithm can achieve a competitive ratio better than Ω 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 in every metric space. A preliminary version of this work appeared in the Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP 2003), Lecture Notes in Computer Science 2719. This work was done while the author was at the Max-Planck-Institut für Informatik, Saarbrücken, Germany, and was partially supported by the Future and Emerging Technologies programme of the EU under contract number IST-1999-14186 (ALCOM–FT). |
| |
Keywords: | Online algorithms Competitive analysis Metric facility location |
本文献已被 SpringerLink 等数据库收录! |
|