SPEAKER: Stephane Durocher, McGill University
TITLE: Geometric Facility Location under Continuous Motion
ABSTRACT:
The traditional problems of facility location are defined statically; given
a set of client positions, a solution consists of a set of facility
positions that optimizes an objective function of the distances between
clients and facilities. In the k-centre problem, the objective is to select
k facilities such that the maximum distance from any client to its nearest
facility is minimized. In the k-median problem, the corresponding average
distance is minimized. In this talk I examine facility location problems in
the mobile setting, where each client follows a continuous trajectory under
bounded velocity. Approximation is necessary since mobile facilities located
at the exact k-centre or k-median involve either unbounded velocity or
discontinuous motion. The goal is to define a set of functions,
corresponding to positions for mobile facilities, that provide a good
approximation to the k-centre or k-median while maintaining motion that is
continuous and whose magnitude of velocity has a low fixed upper bound.
These additional constraints lead to a trade-off between velocity and
approximation factor, requiring new approximation strategies quite different
from previous static approximations. This work identifies existing functions
and introduces new functions that provide bounded-velocity approximations to
the mobile k-centre and k-median, and presents efficient kinetic algorithms
for maintaining these. This is joint work with David Kirkpatrick.