2003 | OriginalPaper | Buchkapitel
On the Competitive Ratio for Online Facility Location
verfasst von : Dimitris Fotakis
Erschienen in: Automata, Languages and Programming
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 Θ(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 achieving a competitive ratio of O(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.