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.