The Kinetic Facility Location Problem

J. Gehweiler, C. Lammersen, B. Degener, in: Proceedings of the 24th European Workshop on Computational Geometry, 2008, pp. 251–254.

Download
No fulltext has been uploaded.
Conference Paper | English
Author
; ;
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 sum of the maintenance cost for the facilities and the connection cost for the clients is at most a constant factor larger than the current optimal cost. In our scenario, each point can open a facility and moves continuously along a known trajectory in a d-dimensional Euclidean space where d is a constant. Our kinetic data structure has a storage requirement of O(n (log^d(n)+log(nR))), where n is the number of points and R is the ratio of the product of the maximum maintenance cost and demand to the product of their corresponding minimum values. In the case that each trajectory can be described by a bounded degree polynomial, the data structure processes O(n^2 log^2(nR)) events, each requiring only O(log(nR)) facility changes and O(log^(d+1)(n) log(nR)) time. This results in a total processing time of O(n^2 log^(d+1)(n) log^3(nR)). To the best of our knowledge, this is the first kinetic data structure for the facility location problem.
Publishing Year
Proceedings Title
Proceedings of the 24th European Workshop on Computational Geometry
Page
251-254
LibreCat-ID

Cite this

Gehweiler J, Lammersen C, Degener B. The Kinetic Facility Location Problem. In: Proceedings of the 24th European Workshop on Computational Geometry. ; 2008:251-254.
Gehweiler, J., Lammersen, C., & Degener, B. (2008). The Kinetic Facility Location Problem. In Proceedings of the 24th European Workshop on Computational Geometry (pp. 251–254).
@inproceedings{Gehweiler_Lammersen_Degener_2008, title={The Kinetic Facility Location Problem}, booktitle={Proceedings of the 24th European Workshop on Computational Geometry}, author={Gehweiler, Joachim and Lammersen, Christiane and Degener, Bastian}, year={2008}, pages={251–254} }
Gehweiler, Joachim, Christiane Lammersen, and Bastian Degener. “The Kinetic Facility Location Problem.” In Proceedings of the 24th European Workshop on Computational Geometry, 251–54, 2008.
J. Gehweiler, C. Lammersen, and B. Degener, “The Kinetic Facility Location Problem,” in Proceedings of the 24th European Workshop on Computational Geometry, 2008, pp. 251–254.
Gehweiler, Joachim, et al. “The Kinetic Facility Location Problem.” Proceedings of the 24th European Workshop on Computational Geometry, 2008, pp. 251–54.

Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar