Approximation algorithm for the kinetic robust \(k\)-center problem. (English) Zbl 1196.65102
A clustering algorithm is developed by generalizing the standard \(k\)-center problem within the context of kinetic data, assuming that the data points are in continuous motion and robust optimization in the presence of heterogeneous data and outliers. Since the \(k\)-center problem has exponential complexity in \(k\), the algorithm provides an approximation to the \(k\)-center problem.
The authors give all the details and properties of the algorithm. Because the problem that the authors handle is very important and new, the performance of the algorithm should be test in real applications
The authors give all the details and properties of the algorithm. Because the problem that the authors handle is very important and new, the performance of the algorithm should be test in real applications
Reviewer: Bülent Karasözen (Ankara)
MSC:
| 65K05 | Numerical mathematical programming methods |
| 62H30 | Classification and discrimination; cluster analysis (statistical aspects) |
| 90C15 | Stochastic programming |
| 65C60 | Computational problems in statistics (MSC2010) |
Keywords:
clustering; kinetic data structures; robust statistics; algorithm; \(k\)-center problem; exponential complexity; algorithmReferences:
| [2] | Albers, G.; Guibas, L. J.; Mitchell, J. S.B.; Roos, T., Voronoi diagrams of moving points, International Journal of Computational Geometry Applications, 8, 365-380 (1998) · Zbl 1035.68520 |
| [4] | Atallah, M. J., Some dynamic computational geometry problems, Computers & Mathematics with Applications, 11, 12, 1171-1181 (1985) · Zbl 0586.68085 |
| [5] | Basch, J.; Guibas, L. J., Data structures for mobile data, Journal of Algorithms, 31, 1, 1-28 (April 1999) · Zbl 0928.68034 |
| [7] | Chang, M. M.; Tekalp, A. M.; Sezan, M. I., Simultaneous motion estimation and segmentation, IEEE Trans. on Image Processing, 6, 9, 1326-1333 (1997) |
| [11] | Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C., Introduction to Algorithms (2001), MIT Press · Zbl 1047.68161 |
| [12] | Cuena, J.; Hernandez, J.; Molina, M., Knowledge-based models for adaptive traffic management systems, Transportation Research Part C: Emerging Technologies, 3, 5, 311-337 (October 1995) |
| [13] | da Fonseca, G. D.; Mount, D. M., Approximate range searching: The absolute model, Computational Geometry: Theory and Applications, 43, 434-444 (2010) · Zbl 1208.65031 |
| [14] | Degener, B.; Gehweiler, J.; Lammersen, C., The kinetic facility location problem, Algorithmica (2008) · Zbl 1155.68371 |
| [15] | Demaine, E. D.; Fomin, F. V.; Hajiaghayi, M.; Thilikos, D. M., Fixed-parameter algorithms for the \((k, r)\)-center in planar graphs and map graphs, ACM Transactions on Algorithms, 1, 1, 33-47 (July 2005) · Zbl 1321.05256 |
| [16] | Deng, Y.; Manjunath, B. S., NeTra-V: Toward an object-based video representation, IEEE Trans. on Circuits and Systems for Video Technology, 8, 5, 616-627 (1998) |
| [18] | Gao, J.; Guibas, L. J.; Nguyen, A., Deformable spanners and applications, Computational Geometry: Theory and Applications, 35, 1, 2-19 (2006) · Zbl 1102.65024 |
| [19] | Gillmann, R., Accuracy assessment of traffic monitoring devices vehicle by vehicle, Transportation Research Record: Journal of the Transportation Research Board, 1945, 56-60 (2006) |
| [21] | Gonzalez, T., Clustering to minimize the maximum intercluster distance, Theoretical Computer Science, 38, 293-306 (1985) · Zbl 0567.62048 |
| [23] | Gribbon, A. P., Field test of nonintrusive traffic detection technologies, Math. Comput. Modelling, 27, 9-11, 349-352 (1998) |
| [24] | Guibas, L., Kinetic data structures, (Mehta, D.; Sahni, S., Handbook of Data Structures and Applications (2004), Chapman and Hall/CRC), 23-1-23-18 |
| [26] | Gupta, P.; Janardan, R.; Smid, M., Fast algorithms for collision and proximity problems involving moving geometric objects, Computational Geometry: Theory and Applications, 6, 371-391 (1996) · Zbl 0857.68107 |
| [27] | Har-Peled, S., Clustering motion, Discrete & Computational Geometry, 31, 4, 545-565 (2004) · Zbl 1094.68103 |
| [28] | (Hochbaum, D. S., Approximation Algorithms for NP-Hard Problems (1995), PWS Publishing Co.: PWS Publishing Co. Boston) · Zbl 1368.68010 |
| [29] | Hochbaum, D. S.; Shmoys, D. B., A best possible heuristic for the \(k\)-center problem, Mathematics of Operations Research, 10, 2, 180-184 (1985) · Zbl 0565.90015 |
| [30] | Kariv, O.; Hakimi, S., An algorithmic approach to network location problems. Part 1: The \(p\)-centers, SIAM Journal on Appl. Math., 37, 513-538 (1979) · Zbl 0432.90074 |
| [33] | McCutchen, R. M.; Khuller, S., Streaming algorithms for \(k\)-center clustering with outliers and with anonymity, (Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Lecture Notes in Computer Science, vol. 5171 (2008)), 165-178 · Zbl 1159.68672 |
| [34] | Plesnik, J., On the computational complexity of centers locating in a graph, Applications of Mathematics, 25, 6, 445-452 (1980) · Zbl 0454.68026 |
| [35] | Plesnik, J., A heuristic for the \(p\)-center problem in graphs, Discrete Applied Math., 17, 3, 263-268 (1987) · Zbl 0637.05020 |
| [36] | Rousseeuw, P. J.; Leroy, A., Robust Regression and Outlier Detection (1987), Wiley: Wiley New York · Zbl 0711.62030 |
| [37] | Saunier, N.; Sayed, T., Automated analysis of road safety with video data, Transportation Research Record: Journal of the Transportation Research Board, 2019, 57-64 (2007) |
| [40] | Wang, D., Unsupervised video segmentation based on watersheds and temporal tracking, IEEE Trans. on Circuits and Systems for Video Technology, 8, 5, 539-546 (1998) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
