Article ID: | iaor20114092 |
Volume: | 19 |
Issue: | 2 |
Start Page Number: | 191 |
End Page Number: | 200 |
Publication Date: | Jun 2011 |
Journal: | Central European Journal of Operations Research |
Authors: | Imreh Csand, Divki Gabriella |
Keywords: | demand, facilities |
In the online facility location problem demand points arrive one at a time and the goal is to decide where and when to open a facility. In this paper we consider a new version of the online facility location problem, where the algorithm is allowed to move the opened facilities in the metric space. We consider the uniform case where each facility has the same constant cost. We present an algorithm which is 2‐competitive for the general case and we prove that it is 3/2‐competitive if the metric space is the line. We also prove that no algorithm with smaller competitive ratio than