The Kinetic Facility Location Problem | SpringerLink
Skip to main content

The Kinetic Facility Location Problem

  • Conference paper
Algorithm Theory – SWAT 2008 (SWAT 2008)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 5124))

Included in the following conference series:

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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 10295
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Agarwal, P., Guibas, L., Hershberger, J., Veach, E.: Maintaining the Extent of a Moving Point Set. Discrete & Computational Geometry 26(3), 353–374 (2001)

    MATH  MathSciNet  Google Scholar 

  2. Agarwal, P., Har-Peled, S., Varadarajan, K.: Approximating Extent Measures of Points. Journal of the ACM 51(4), 606–635 (2004)

    Article  MathSciNet  Google Scholar 

  3. 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)

    Google Scholar 

  4. Basch, J., Guibas, L., Hershberger, J.: Data Structures for Mobile Data. Journal of Algorithms 31(1), 1–28 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  5. Basch, J., Guibas, L., Zhang, L.: Proximity Problems on Moving Points. In: Proc. 13th Symposium on Computational Geometry, pp. 344–351 (1997)

    Google Scholar 

  6. 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)

    Google Scholar 

  7. Czumaj, A., Frahling, G., Sohler, C.: Efficient Kinetic Data Structures for MaxCut. In: Proc. 19th Canadian Conference on Computational Geometry, pp. 157–160 (2007)

    Google Scholar 

  8. Degener, B., Gehweiler, J., Lammersen, C.: The Kinetic Facility Location Problem. Technical Report tr-ri-08-2880, University of Paderborn (2008)

    Google Scholar 

  9. Gao, J., Guibas, L., Nguyen, A.: Deformable Spanners and Applications. In: Proc. 20th Symposium on Computational Geometry, pp. 190–199 (2004)

    Google Scholar 

  10. Gao, J., Guibas, L., Hershberger, J., Zhang, L., Zhu, A.: Discrete Mobile Centers. Journal of Discrete and Computational Geometry 30(1), 45–63 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  11. 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)

    Google Scholar 

  12. Guibas, L.: Kinetic Data Structures: A State of the Art Report. In: Proc. 3rd Workshop on Algorithmic Foundations of Robotics, pp. 191–209 (1998)

    Google Scholar 

  13. Har-Peled, S.: Clustering Motion. In: Proc. 42nd IEEE Symposium on Foundations of Computer Science, pp. 84–93 (2001)

    Google Scholar 

  14. Hershberger, J.: Smooth Kinetic Maintenance of Clusters. In: Proc. Symposium on Computational Geometry, pp. 48–57 (2003)

    Google Scholar 

  15. Indyk, P.: Algorithms for Dynamic Geometric Problems over Data Streams. In: Proc. 36th ACM Symposium on Theory of Computing, pp. 373–380 (2004)

    Google Scholar 

  16. 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)

    Google Scholar 

  17. 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)

    Article  MathSciNet  Google Scholar 

  18. 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)

    Article  MATH  MathSciNet  Google Scholar 

  19. Mettu, R.R., Plaxton, C.G.: The Online Median Problem. SIAM J. Comput. 32(3), 816–832 (2003)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

Joachim Gudmundsson

Rights and permissions

Reprints 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)

Publish with us

Policies and ethics