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. 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 \(\mathcal{O}(n (\log^{d}(n)+\log(nR)))\) space, where \(R:=\frac{\max_{p_i \in \mathcal{P}}{f_i} \,\cdot\, \max_{p_i\in \mathcal{P}}{d_i}}{\min_{p_i \in \mathcal{P}}{f_i} \,\cdot\, \min_{p_i\in \mathcal{P}}{d_i}}\), \(\mathcal{P} = \{ p_1, p_2, \ldots , p_n \}\) is the set of given points, and f i , d i are the maintenance cost and the demand of a point p i , respectively. In case that each trajectory can be described by a bounded degree polynomial, we process \(\mathcal{O}(n^2 \log^2(nR))\) events, each requiring \(\mathcal{O}(\log^{d+1}(n) \cdot \log(nR))\) time and \(\mathcal{O}(\log(nR))\) status changes. To the best of our knowledge, this is the first kinetic data structure for the facility location problem.
Partially supported by the EU within FP7-ICT-2007-1 under contract no. 215270 (FRONTS), DFG-project “Smart Teams” within the SPP 1183 “Organic Computing”, and DFG grant Me 872/8-3.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Agarwal, P., Guibas, L., Hershberger, J., Veach, E.: Maintaining the Extent of a Moving Point Set. Discrete & Computational Geometry 26(3), 353–374 (2001)
Agarwal, P., Har-Peled, S., Varadarajan, K.: Approximating Extent Measures of Points. Journal of the ACM 51(4), 606–635 (2004)
Bădoiu, M., Czumaj, A., Indyk, P., Sohler, C.: Facility Location in Sublinear Time. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 866–877. Springer, Heidelberg (2005)
Basch, J., Guibas, L., Hershberger, J.: Data Structures for Mobile Data. Journal of Algorithms 31(1), 1–28 (1999)
Basch, J., Guibas, L., Zhang, L.: Proximity Problems on Moving Points. In: Proc. 13th Symposium on Computational Geometry, pp. 344–351 (1997)
Bespamyatnikh, S., Bhattacharya, B., Kirkpatrick, D., Segal, M.: Mobile Facility Location. In: Proc 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, pp. 46–53 (2000)
Czumaj, A., Frahling, G., Sohler, C.: Efficient Kinetic Data Structures for MaxCut. In: Proc. 19th Canadian Conference on Computational Geometry, pp. 157–160 (2007)
Degener, B., Gehweiler, J., Lammersen, C.: The Kinetic Facility Location Problem. Technical Report tr-ri-08-2880, University of Paderborn (2008)
Gao, J., Guibas, L., Nguyen, A.: Deformable Spanners and Applications. In: Proc. 20th Symposium on Computational Geometry, pp. 190–199 (2004)
Gao, J., Guibas, L., Hershberger, J., Zhang, L., Zhu, A.: Discrete Mobile Centers. Journal of Discrete and Computational Geometry 30(1), 45–63 (2003)
Gehweiler, J., Lammersen, C., Sohler, C.: A Distributed O(1)-Approximation Algorithm for the Uniform Facility Location Problem. In: Proc. 18th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 237–243 (2006)
Guibas, L.: Kinetic Data Structures: A State of the Art Report. In: Proc. 3rd Workshop on Algorithmic Foundations of Robotics, pp. 191–209 (1998)
Har-Peled, S.: Clustering Motion. In: Proc. 42nd IEEE Symposium on Foundations of Computer Science, pp. 84–93 (2001)
Hershberger, J.: Smooth Kinetic Maintenance of Clusters. In: Proc. Symposium on Computational Geometry, pp. 48–57 (2003)
Indyk, P.: Algorithms for Dynamic Geometric Problems over Data Streams. In: Proc. 36th ACM Symposium on Theory of Computing, pp. 373–380 (2004)
Jain, K., Mahdian, M., Saberi, A.: A New Greedy Approach for Facility Location Problems. In: Proc. 34th ACM Symposium on Theory of Computing, pp. 731–740 (2002)
Jain, K., Vazirani, V.: Approximation Algorithms for Metric Facility Location and k-Median Problems Using the Primal-Dual Schema and Lagrangian Relaxation. Journal of the ACM 48(2), 274–296 (2001)
Kolliopoulos, S., Rao, S.: A Nearly Linear-Time Approximation Scheme for the Euclidean k-Median Problem. SIAM Journal on Computing 37(3), 757–782 (2007)
Mettu, R.R., Plaxton, C.G.: The Online Median Problem. SIAM J. Comput. 32(3), 816–832 (2003)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Degener, B., Gehweiler, J., Lammersen, C. (2008). The Kinetic Facility Location Problem. In: Gudmundsson, J. (eds) Algorithm Theory – SWAT 2008. SWAT 2008. Lecture Notes in Computer Science, vol 5124. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-69903-3_34
Download citation
DOI: https://doi.org/10.1007/978-3-540-69903-3_34
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-69900-2
Online ISBN: 978-3-540-69903-3
eBook Packages: Computer ScienceComputer Science (R0)