Authors: Amitai Armon Iftah Gamzu Danny Segev
Publish Date: 2012/10/25
Volume: 28, Issue: 2, Pages: 358-375
Abstract
An instance of the mobile facility location problem consists of a complete directed graph G = V E in which each arc u v in E is associated with a numerical attribute mathcal M uv representing the cost of moving any object from u to v An additional ingredient of the input is a collection of servers S = s 1 ldots s k and a set of clients C = c 1 ldots c ell which are located at nodes of the underlying graph With this setting in mind a movement scheme is a function psi S rightarrow V that relocates each server s i to a new position psi s i We refer to mathcal M s i psi s i as the relocation cost of s i and to min i in k mathcal M c j psi s i the cost of assigning client c j to the nearest final server location as the service cost of c j The objective is to compute a movement scheme that minimizes the sum of relocation and service costs In this paper we resolve an open question posed by Demaine et al SODA ’07 by characterizing the approximability of mobile facility location through LPbased methods We also develop a more efficient algorithm which is based on a combinatorial filtering approach The latter technique is of independent interest as it may be applicable in other settings as well In this context we introduce a weighted version of the occupancy problem for which we establish interesting tail bounds not before demonstrating that existing bounds cannot be extended
Keywords: