Mobile facility location

Mobile facility location problem is related to the location of mobile facilities serving a set of points moving continuously in the plane. Examples of such problems are the maintenance of the $p$-center and $p$-median for moving points under the $L_p$ metric. This problem has applications in mobile wireless communication networks when the broadcast range should contain all the customers getting service. Mobile facility location problem is first introduced in [17].

In [17,18] we focused on exact and approximate versions of the 1-center and 1-median problems where the facility is constrained to have bounded velocity. We insist that the facilities move continuously. These restricted instances pose several challenging algorithmic and geometric questions. The results obtained so far are summarized below [17,18,36].

• 1-center
  It is easy to show that the velocity of rectilinear 1-center is bounded by $\sqrt{2}$ and the rectilinear 1-center can be maintained in an efficient KDS. Euclidean 1-center may move with arbitrarily high speed. When the facility is allowed to move with unit velocity, the center of mass of points is a good approximation of Euclidean 1-center which guarantees an approximation factor of $2-\frac{2}{n}$ and is shown to be asymptotically optimal. The center of the smallest bounding box of any set of points in the plane provides a $(1+\sqrt{2})/2$-approximat ion of the Euclidean 1-center, and this value is tight. In this case the speed of the facility is at most $\sqrt{2}$. Finally, we are able to show that for every $\epsilon > 0$, any $(1+\epsilon)$-approximate mobile Euclidean 1-center has velocity at least $1/(8\sqrt{\epsilon}))$ in worst case. The Steiner center provides a 1.1153-approximation of the Euclidean 1-center (the exact value is an irrational equation root) and has velocity at most $4/\pi$; both bounds are tight. These results appear in [35] and [36].

• 1-median
  Not only does the Euclidean 1-median have unbounded velocity in two dimensions, but there are sets of mobile points for which the motion of the Euclidean 1-median is discontinuous. The centre of mass provides a $(2-2/n)$-approximation of the Euclidean 1-median (still with unit velocity); this bound is tight. We introduce a new approximation to the Euclidean 1-median which we call the projection median. The projection median guarantees a $(4/\pi)$-approximation of the Euclidean 1-median but cannot guarantee any approximation factor less than $\sqrt{4/\pi2 + 1}$. The velocity of the projection median is at most $4/\pi$; this bound is tight. These results appear in [36] and [37] and have been submitted for journal publication.

• 2-center
  The Euclidean 2-center, rectilinear 2-center, and 2-means center (generalization of the centre of mass) are all discontinuous in two or more dimensions. Using the rectilinear 1-center or the Steiner centre as a centre of reflection, we are able to define two approximations to the Euclidean 2-center that guarantee approximations of $2\sqrt{2}$ (tight) and $8/\pi$ (lower bound $2\sqrt{1+1/\pi2}$), respectively. The correponding bounds on velocity are $2\sqrt{2}+1$ and $8/\pi+1$. These results appear in [36] and have been submitted for journal publication.

• 3-center and 2-median
  Even in one dimension, no bounded-velocity approximation of the Euclidean 3-center is possible. Similarly, no bounded-velocity approximation of the Euclidean 2-median is possible. Of course, these results apply to the rectilinear case as well since all $\ell_p$ norms are equal in one dimension. These results appear in [36].