Geometric Facility Location under Continuous Motion.

Stephane Durocher University of British Columbia

DEPARTMENT SEMINAR DATE: Tuesday, March 28, 2006 TIME: 3:00 pm PLACE: Thorvaldson 271 This is a recruitment seminar. *** Everyone is welcome ***

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.

About the speaker

Stephane Durocher is defending his Ph.D. thesis in Computer Science in March 2006 at the University of British Columbia. He holds an M.Sc. (1999) degree in Computer Science from the University of British Columbia and a B.Sc. (1997) degree in Computer Science and Mathematics from the University of Toronto. Stephane's research spans several areas within theoretical computer science, including a specialization in computational geometry and interests in graph theory, data structures, complexity, algorithm analysis, and combinatorics, with applications in mobile computing, operations research, robotics, statistics, numerical computation, VLSI design, and network routing. Stephane has a keen interest in teaching and has instructed three courses at UBC covering topics in theoretical computer science and discrete mathematics.

[an error occurred while processing this directive]