Premium
Obtaining online approximation algorithms for facility dispersion from offline algorithms
Author(s) -
Rosenkrantz Daniel J.,
Tayi Giri K.,
Ravi S.S.
Publication year - 2006
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20109
Subject(s) - algorithm , online algorithm , computer science , approximation algorithm , enhanced data rates for gsm evolution , context (archaeology) , competitive analysis , a priori and a posteriori , facility location problem , mathematics , monotonic function , triangle inequality , mathematical optimization , discrete mathematics , upper and lower bounds , artificial intelligence , paleontology , mathematical analysis , philosophy , epistemology , biology
Abstract Facility dispersion problems arise in the context of placing obnoxious facilities and retail outlets. In the offline version of such a problem, the input consists of a complete graph on n nodes, a nonnegative weight (distance) for each edge, and the number k ⩽ n of facilities to be placed. The goal is to choose a facility placement consisting of k nodes so as to maximize a given measure of the distances among the facilities. Here, we consider an online version of the problem where the value of k is not known apriori; instead, requests for facilities arrive one at a time. It is also required that previously placed facilities cannot be moved or eliminated. Our main result is that for any objective that satisfies two properties, namely monotonicity and graceful degradation, any offline approximation algorithm with a performance guarantee ρ can be used to develop an algorithm with competitive ratio c ρ for the online version, where c is a constant independent of the problem instance. Objectives for which our result applies include the average edge weight and average weight of a star subgraph. The result holds even when the edge weights do not satisfy the triangle inequality. We also identify dispersion objectives for which the offline and online versions have different behaviors when only one of the above two properties is satisfied. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 47(4), 206–217 2006