Online facility location with facility movements

Online facility location with facility movements

0.00 Avg rating0 Votes
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: ,
Keywords: demand, facilities
Abstract:

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 ( 13 + 1 ) / 4 1.1514 equ1 exists. We also present an empirical analysis which shows that the algorithm gives very good results in the average case.

Reviews

Required fields are marked *. Your email address will not be published.