Approximation algorithm for the kinetic robust K-center problem

P.K. Agarwal, J.M. Phillips, An efficient algorithm for 2D Euclidean 2-center with outliers, in: Proc. of the 16th European Symposium on Algorithms, 2008, pp. 64–75 Albers, 1998, Voronoi diagrams of moving points, International Journal of Computational Geometry Applications, 8, 365, 10.1142/S0218195998000187 N.J. Alewine, J.C. Colson, A.P. Ittycheriah, S.H. Maes, P.A. Moskowitz, Automated traffic mapping, U.S. Patent 6150961, filed November 24, 1998, and issued November 21, 2000 Atallah, 1985, Some dynamic computational geometry problems, Computers & Mathematics with Applications, 11, 1171, 10.1016/0898-1221(85)90105-1 Basch, 1999, Data structures for mobile data, Journal of Algorithms, 31, 1, 10.1006/jagm.1998.0988 J. Basch, L.J. Guibas, L. Zhang, Proximity problems on moving points, in: Proc. of the 13th ACM Symposium on Computational Geometry, 1997, pp. 344–351 Chang, 1997, Simultaneous motion estimation and segmentation, IEEE Trans. on Image Processing, 6, 1326, 10.1109/83.623196 M. Charikar, S. Khuller, D.M. Mount, G. Narasimhan, Algorithms for facility location problems with outliers, in: Proc. of the 12th ACM Symposium on Discrete Algorithms, 2001, pp. 642–651 K. Chen, A constant factor approximation algorithm for k-median clustering with outliers, in: Proc. of the 19th ACM Symposium on Discrete Algorithms, 2008, pp. 826–835 R. Cole, L.-A. Gottlieb, Searching dynamic point sets in spaces with bounded doubling dimension, in: Proc. of the 38th ACM Symposium on Theory of Computing, 2006, pp. 574–583 Cormen, 2001 Cuena, 1995, Knowledge-based models for adaptive traffic management systems, Transportation Research Part C: Emerging Technologies, 3, 311, 10.1016/0968-090X(95)00013-9 da Fonseca, 2010, Approximate range searching: The absolute model, Computational Geometry: Theory and Applications, 43, 434, 10.1016/j.comgeo.2008.09.009 Degener, 2008, The kinetic facility location problem, Algorithmica Demaine, 2005, Fixed-parameter algorithms for the (k,r)-center in planar graphs and map graphs, ACM Transactions on Algorithms, 1, 33, 10.1145/1077464.1077468 Deng, 1998, NeTra-V: Toward an object-based video representation, IEEE Trans. on Circuits and Systems for Video Technology, 8, 616, 10.1109/76.718508 T. Feder, D. Greene, Optimal algorithms for approximate clustering, in: Proc. of the 20th ACM Symposium on Theory of Computing, 1988, pp. 434–444 Gao, 2006, Deformable spanners and applications, Computational Geometry: Theory and Applications, 35, 2, 10.1016/j.comgeo.2005.10.001 Gillmann, 2006, Accuracy assessment of traffic monitoring devices vehicle by vehicle, Transportation Research Record: Journal of the Transportation Research Board, 1945, 56, 10.3141/1945-07 A.R. Golding, Automobile navigation system with dynamic traffic data, U.S. Patent 5933100, filed December 27, 1995, and issued August 3, 1999 Gonzalez, 1985, Clustering to minimize the maximum intercluster distance, Theoretical Computer Science, 38, 293, 10.1016/0304-3975(85)90224-5 L.-A. Gottlieb, L. Roditty, An optimal dynamic spanner for doubling metric spaces, in: Proc. of the 16th European Symposium on Algorithms, 2008, pp. 478–489 Gribbon, 1998, Field test of nonintrusive traffic detection technologies, Math. Comput. Modelling, 27, 349, 10.1016/S0895-7177(98)00069-7 Guibas, 2004, Kinetic data structures, 23-1 L.J. Guibas, Kinetic data structures: A state of the art report, in: Proc. of the Third Workshop on the Algorithmic Foundations of Robotics, 1998, pp. 191–209 Gupta, 1996, Fast algorithms for collision and proximity problems involving moving geometric objects, Computational Geometry: Theory and Applications, 6, 371, 10.1016/0925-7721(95)00028-3 Har-Peled, 2004, Clustering motion, Discrete & Computational Geometry, 31, 545, 10.1007/s00454-004-2822-7 1995 Hochbaum, 1985, A best possible heuristic for the k-center problem, Mathematics of Operations Research, 10, 180, 10.1287/moor.10.2.180 Kariv, 1979, An algorithmic approach to network location problems. Part 1: The p-centers, SIAM Journal on Appl. Math., 37, 513, 10.1137/0137040 S.-W. Kim, Y. Eun, H. Kim, J. Ko, W.-J. Jung, Y.K. Choi, Y.G. Cho, D.-I. Cho, Performance comparison of loop/piezo and ultrasonic sensor-based traffic detection systems for collecting individual vehicle information, in: Proc. of 6th World Cong. on Intelligent Transport Systems, 1998 (CD-ROM) R. Krauthgamer, J.R. Lee, Navigating nets: Simple algorithms for proximity search, in: Proc. of the 15th ACM Symposium on Discrete Algorithms, 2004, pp. 798–807 McCutchen, 2008, Streaming algorithms for k-center clustering with outliers and with anonymity, vol. 5171, 165 Plesnik, 1980, On the computational complexity of centers locating in a graph, Applications of Mathematics, 25, 445, 10.21136/AM.1980.103883 Plesnik, 1987, A heuristic for the p-center problem in graphs, Discrete Applied Math., 17, 263, 10.1016/0166-218X(87)90029-1 Rousseeuw, 1987 Saunier, 2007, Automated analysis of road safety with video data, Transportation Research Record: Journal of the Transportation Research Board, 2019, 57, 10.3141/2019-08 E. Schomer, C. Theil, Efficient collision detection for moving polyhedra, in: Proc. of the 11th ACM Symposium on Computational Geometry, 1995, pp. 51–60 E. Schomer, C. Theil, Subquadratic algorithms for the general collision detection problem, in: Abstracts 12th European Workshop Comput. Geom., 1996, pp. 95–101 Wang, 1998, Unsupervised video segmentation based on watersheds and temporal tracking, IEEE Trans. on Circuits and Systems for Video Technology, 8, 539, 10.1109/76.718501 Z. Wang, S. Elbaum, D.S. Rosenblum, Automated generation of context-aware tests, in: Proc. of the 29th International Conference on Software Engineering, 2007, pp. 406–415