Kinetic Facility Location
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. Our kinetic data structure requires O(n(log(d)(n)+ log(nR))) space in total, where R := max(pi is an element of P) f(i).max(pi is an element of P)d(i)/min(pi is an element of P) f(i).min(pi is an element of P) d(i), P = {p(1), p(2), ... , p(n)} is the set of given points, and f(i), d(i) are the maintenance cost and the demand of a point pi, respectively. In case that each trajectory can be described by a bounded degree polynomial, we process O(n(2) log(2)(nR)) events, each requiring O(log(d+1)(n).log(nR)) time and O(log(nR)) status changes.
facility location kinetic data structure approximation algorithm deterministic algorithm