Kinetic Facility Location |
| |
Authors: | Bastian Degener Joachim Gehweiler Christiane Lammersen |
| |
Affiliation: | (1) Department of Computer Science, University of Texas at Dallas, Richardson, TX 75083, USA;(2) School of Computing Science, Simon Fraser University, Burnaby, B.C., Canada, V5A 1S6;(3) Department of Computer Science, University of British Columbia, Vancouver, B.C., Canada, V6T 1Z4;(4) Communication Systems Engineering Department, Ben-Gurion University of the Negev, Beer-Sheva, 84105, Israel |
| |
Abstract: | We present a deterministic kinetic data structure for the facility location problem that maintains a subset of the moving points as facilities such that, at any point of time, the accumulated cost for the whole point set is at most a constant factor larger than the optimal cost. In our scenario, each point can change its status between client and facility and moves continuously along a known trajectory in a d-dimensional Euclidean space, where d is a constant. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|