{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:29:33Z","timestamp":1759638573833,"version":"3.35.0"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2008,11,11]],"date-time":"2008-11-11T00:00:00Z","timestamp":1226361600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2010,7]]},"DOI":"10.1007\/s00453-008-9250-7","type":"journal-article","created":{"date-parts":[[2008,11,10]],"date-time":"2008-11-10T17:06:59Z","timestamp":1226336819000},"page":"562-584","source":"Crossref","is-referenced-by-count":4,"title":["Kinetic Facility Location"],"prefix":"10.1007","volume":"57","author":[{"given":"Bastian","family":"Degener","sequence":"first","affiliation":[]},{"given":"Joachim","family":"Gehweiler","sequence":"additional","affiliation":[]},{"given":"Christiane","family":"Lammersen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2008,11,11]]},"reference":[{"key":"9250_CR1","doi-asserted-by":"crossref","unstructured":"Abam, M., de Berg, M., Poon, S., Speckmann, B.: Kinetic collision detection for convex fat objects. In: Proceedings of the 14th Annual European Symposium on Algorithms (ESA), pp.\u00a04\u201315 (2006)","DOI":"10.1007\/11841036_4"},{"key":"9250_CR2","doi-asserted-by":"crossref","unstructured":"Abam, M., de Berg, M., Speckmann, B.: Kinetic kd-trees and longest-side kd-trees. In: Proceedings of the 23rd Annual Symposium on Computational Geometry, pp.\u00a0364\u2013372 (2007)","DOI":"10.1145\/1247069.1247133"},{"key":"9250_CR3","unstructured":"Agarwal, P., Erickson, J., Guibas, L.: Kinetic binary space partitions for intersecting segments and disjoint triangles. In: Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.\u00a0107\u2013116 (1998)"},{"issue":"2","key":"9250_CR4","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/S0925-7721(00)00005-5","volume":"16","author":"P. Agarwal","year":"2000","unstructured":"Agarwal, P., Guibas, L., Murali, T., Vitter, J.: Cylindrical static and kinetic binary space partitions. Comput. Geom. Theory Appl. 16(2), 103\u2013127 (2000)","journal-title":"Comput. Geom. Theory Appl."},{"issue":"4","key":"9250_CR5","doi-asserted-by":"crossref","first-page":"721","DOI":"10.1007\/s004540010060","volume":"24","author":"P. Agarwal","year":"2000","unstructured":"Agarwal, P., Basch, J., de Berg, M., Guibas, L., Hershberger, J.: Lower bounds for kinetic planar subdivisions. Discrete Comput. Geom. 24(4), 721\u2013733 (2000)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"9250_CR6","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1007\/s00454-001-0019-x","volume":"26","author":"P. Agarwal","year":"2001","unstructured":"Agarwal, P., Guibas, L., Hershberger, J., Veach, E.: Maintaining the extent of a moving point set. Discrete Comput. Geom. 26(3), 353\u2013374 (2001)","journal-title":"Discrete Comput. Geom."},{"key":"9250_CR7","doi-asserted-by":"crossref","unstructured":"Agarwal, P., Gao, J., Guibas, L.: Kinetic medians and kd-trees. In: Proceedings of the 10th Annual European Symposium on Algorithms (ESA), pp.\u00a05\u201316 (2002)","DOI":"10.1007\/3-540-45749-6_5"},{"issue":"1","key":"9250_CR8","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/S0022-0000(02)00035-1","volume":"66","author":"P. Agarwal","year":"2003","unstructured":"Agarwal, P., Arge, L., Erickson, J.: Indexing moving points. J.\u00a0Comput. Syst. Sci. 66(1), 207\u2013243 (2003)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"issue":"4","key":"9250_CR9","first-page":"606","volume":"51","author":"P. Agarwal","year":"2004","unstructured":"Agarwal, P., Har-Peled, S., Varadarajan, K.: Approximating extent measures of points. J.\u00a0ACM 51(4), 606\u2013635 (2004)","journal-title":"J.\u00a0ACM"},{"key":"9250_CR10","doi-asserted-by":"crossref","unstructured":"B\u0103doiu, M., Czumaj, A., Indyk, P., Sohler, C.: Facility location in sublinear time. In: Proceedings of the 32nd Annual International Colloquium on Automata, Languages and Programming (ICALP), vol.\u00a03580, pp.\u00a0866\u2013877 (2005)","DOI":"10.1007\/11523468_70"},{"key":"9250_CR11","doi-asserted-by":"crossref","unstructured":"Basch, J., Guibas, L., Zhang, L.: Proximity problems on moving points. In: Proceedings of the 13th Annual Symposium on Computational Geometry, pp.\u00a0344\u2013351 (1997)","DOI":"10.1145\/262839.262998"},{"issue":"1","key":"9250_CR12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1006\/jagm.1998.0988","volume":"31","author":"J. Basch","year":"1999","unstructured":"Basch, J., Guibas, L., Hershberger, J.: Data structures for mobile data. J.\u00a0Algorithms 31(1), 1\u201328 (1999)","journal-title":"J.\u00a0Algorithms"},{"issue":"3","key":"9250_CR13","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/j.comgeo.2003.11.001","volume":"27","author":"J. Basch","year":"2004","unstructured":"Basch, J., Erickson, J., Guibas, L., Hershberger, J., Zhang, L.: Kinetic collision detection between two simple polygons. Comput. Geom. Theory Appl. 27(3), 211\u2013235 (2004)","journal-title":"Comput. Geom. Theory Appl."},{"key":"9250_CR14","doi-asserted-by":"crossref","unstructured":"Bespamyatnikh, S., Bhattacharya, B., Kirkpatrick, D., Segal, M.: Mobile facility location. In: Proceedings of the 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, pp.\u00a046\u201353 (2000)","DOI":"10.1145\/345848.345858"},{"issue":"4","key":"9250_CR15","doi-asserted-by":"crossref","first-page":"803","DOI":"10.1137\/S0097539701398594","volume":"34","author":"M. Charikar","year":"2005","unstructured":"Charikar, M., Guha, S.: Improved combinatorial algorithms for facility location problems. SIAM J. Comput. 34(4), 803\u2013824 (2005)","journal-title":"SIAM J. Comput."},{"key":"9250_CR16","unstructured":"Czumaj, A., Frahling, G., Sohler, C.: Efficient kinetic data structures for MaxCut. In: Proceedings of the 19th Canadian Conference on Computional Geometry (CCCG), pp.\u00a0157\u2013160 (2007)"},{"key":"9250_CR17","doi-asserted-by":"crossref","unstructured":"Degener, B., Gehweiler, J., Lammersen, C.: The kinetic facility location problem. In: Proceedings of the 11th Scandinavian Workshop on Algorithm Theory (SWAT) (2008)","DOI":"10.1007\/978-3-540-69903-3_34"},{"issue":"1","key":"9250_CR18","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1007\/s00454-003-2925-6","volume":"30","author":"J. Gao","year":"2003","unstructured":"Gao, J., Guibas, L., Hershberger, J., Zhang, L., Zhu, A.: Discrete mobile centers. Discrete Comput. Geom. 30(1), 45\u201363 (2003)","journal-title":"Discrete Comput. Geom."},{"issue":"1\u20132","key":"9250_CR19","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/j.comgeo.2005.10.001","volume":"35","author":"J. Gao","year":"2006","unstructured":"Gao, J., Guibas, L., Nguyen, A.: Deformable spanners and applications. Comput. Geom. 35(1\u20132), 2\u201319 (2006)","journal-title":"Comput. Geom."},{"key":"9250_CR20","doi-asserted-by":"crossref","unstructured":"Gehweiler, J., Lammersen, C., Sohler, C.: A distributed O(1)-approximation algorithm for the uniform facility location problem. In: Proceedings of the 18th ACM Symposium on Parallelism in Algorithms and Architectures, pp.\u00a0237\u2013243 (2006)","DOI":"10.1145\/1148109.1148152"},{"issue":"1","key":"9250_CR21","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1006\/jagm.1998.0993","volume":"31","author":"S. Guha","year":"1999","unstructured":"Guha, S., Khuller, S.: Greedy strikes back: improved facility location algorithms. J.\u00a0Algorithms 31(1), 228\u2013248 (1999)","journal-title":"J.\u00a0Algorithms"},{"key":"9250_CR22","unstructured":"Guibas, L.: Kinetic data structures: a state of the art report. In: Proceedings of the 3rd Workshop on Algorithmic Foundations of Robotics, pp.\u00a0191\u2013209 (1998)"},{"issue":"4","key":"9250_CR23","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1007\/s00454-001-0015-1","volume":"25","author":"L. Guibas","year":"2001","unstructured":"Guibas, L., Hershberger, J., Suri, S., Zhang, L.: Kinetic connectivity for unit disks. Discrete Comput. Geom. 25(4), 591\u2013610 (2001)","journal-title":"Discrete Comput. Geom."},{"issue":"4","key":"9250_CR24","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1007\/s00454-004-2822-7","volume":"31","author":"S. Har-Peled","year":"2004","unstructured":"Har-Peled, S.: Clustering motion. Discrete Comput. Geom. 31(4), 545\u2013565 (2004)","journal-title":"Discrete Comput. Geom."},{"issue":"6","key":"9250_CR25","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/j.ipl.2004.09.005","volume":"92","author":"J. Hershberger","year":"2004","unstructured":"Hershberger, J.: Kinetic collision detection with fast flight plan changes. Inf. Process. Lett. 92(6), 287\u2013291 (2004)","journal-title":"Inf. Process. Lett."},{"issue":"1\u20132","key":"9250_CR26","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/j.comgeo.2004.02.004","volume":"31","author":"J. Hershberger","year":"2005","unstructured":"Hershberger, J.: Smooth kinetic maintenance of clusters. Comput. Geom. Theory Appl. 31(1\u20132), 3\u201330 (2005)","journal-title":"Comput. Geom. Theory Appl."},{"key":"9250_CR27","unstructured":"Hershberger, J., Suri, S.: Simplified kinetic connectivity for rectangles and hypercubes. In: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.\u00a0158\u2013167 (2001)"},{"key":"9250_CR28","doi-asserted-by":"crossref","unstructured":"Indyk, P.: Algorithms for dynamic geometric problems over data streams. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC), pp.\u00a0373\u2013380 (2004)","DOI":"10.1145\/1007352.1007413"},{"issue":"2","key":"9250_CR29","first-page":"274","volume":"48","author":"K. Jain","year":"2001","unstructured":"Jain, K., Vazirani, V.: Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation. J.\u00a0ACM 48(2), 274\u2013296 (2001)","journal-title":"J.\u00a0ACM"},{"key":"9250_CR30","doi-asserted-by":"crossref","unstructured":"Jain, K., Mahdian, M., Saberi, A.: A new greedy approach for facility location problems. In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), pp.\u00a0731\u2013740 (2002)","DOI":"10.1145\/509907.510012"},{"issue":"3","key":"9250_CR31","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/j.comgeo.2003.11.001","volume":"27","author":"D. Kirkpatrick","year":"2004","unstructured":"Kirkpatrick, D., Snoeyink, J., Speckmann, B.: Kinetic collision detection for two simple polygons. Comput. Geom. Theory Appl. 27(3), 211\u2013235 (2004)","journal-title":"Comput. Geom. Theory Appl."},{"issue":"3","key":"9250_CR32","doi-asserted-by":"crossref","first-page":"757","DOI":"10.1137\/S0097539702404055","volume":"37","author":"S. Kolliopoulos","year":"2007","unstructured":"Kolliopoulos, S., Rao, S.: A nearly linear-time approximation scheme for the Euclidean k-median problem. SIAM J. Comput. 37(3), 757\u2013782 (2007)","journal-title":"SIAM J. Comput."},{"key":"9250_CR33","doi-asserted-by":"crossref","unstructured":"Lammersen, C., Sohler, C.: Facility location in dynamic geometric data streams. In: Proceedings of the 16th Annual European Symposium on Algorithms (ESA), pp.\u00a0660\u2013671 (2008)","DOI":"10.1007\/978-3-540-87744-8_55"},{"key":"9250_CR34","doi-asserted-by":"crossref","unstructured":"Mahdian, M., Ye, Y., Zhang, J.: Improved approximation algorithms for metric facility location problems. In: Proceedings of the 5th International Workshop on Approximation Algorithms of Combinatorial Optimization Problems (APPROX), pp.\u00a0229\u2013242 (2002)","DOI":"10.1007\/3-540-45753-4_20"},{"issue":"3","key":"9250_CR35","doi-asserted-by":"crossref","first-page":"816","DOI":"10.1137\/S0097539701383443","volume":"32","author":"R.R. Mettu","year":"2003","unstructured":"Mettu, R.R., Plaxton, C.G.: The online median problem. SIAM J. Comput. 32(3), 816\u2013832 (2003)","journal-title":"SIAM J. Comput."},{"key":"9250_CR36","doi-asserted-by":"crossref","unstructured":"Moscibroda, T., Wattenhofer, R.: Facility location: distributed approximation. In: Proceedings of the 24th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, pp.\u00a0108\u2013117 (2005)","DOI":"10.1145\/1073814.1073834"},{"key":"9250_CR37","doi-asserted-by":"crossref","unstructured":"Shmoys, D.B., Tardos, E., Aardal, K.: Approximation algorithms for facility location problems. In: Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC), pp.\u00a0265\u2013274 (1997)","DOI":"10.1145\/258533.258600"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9250-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-008-9250-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9250-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,2]],"date-time":"2025-02-02T16:28:48Z","timestamp":1738513728000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-008-9250-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,11,11]]},"references-count":37,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,7]]}},"alternative-id":["9250"],"URL":"https:\/\/doi.org\/10.1007\/s00453-008-9250-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2008,11,11]]}}}