Fully polynomial-time approximation scheme for a special case of a quadratic Euclidean 2-clustering problem

A. V. Kel'manov   ; V. I. Khandeev

Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 56 (2016) no. 2, pp. 332-340

Résumé

The strongly NP-hard problem of partitioning a finite set of points of Euclidean space into two clusters of given sizes (cardinalities) minimizing the sum (over both clusters) of the intracluster sums of squared distances from the elements of the clusters to their centers is considered. It is assumed that the center of one of the sought clusters is specified at the desired (arbitrary) point of space (without loss of generality, at the origin), while the center of the other one is unknown and determined as the mean value over all elements of this cluster. It is shown that unless P = NP, there is no fully polynomial-time approximation scheme for this problem, and such a scheme is substantiated in the case of a fixed space dimension.

Bibliographie

[1] Bern M., Eppstein D., “Approximation algorithms for geometric problems”, Approximation algorithms for NP-hard problems, eds. Hochbaum D. S., PWS Publishing Co., Boston, 1997, 296–345

[2] James G., Witten D., Hastie T., Tibshirani R., An Introduction to statistical learning, Springer Science+Business Media, LLC, New York, 2013 | MR | Zbl

[3] Bishop M. C., Pattern recognition and machine learning, Springer Science+Business Media, LLC, New York, 2006 | MR | Zbl

[4] Flach P., Machine learning: the art and science of algorithms that make sense of data, Cambridge University Press, New York, 2012 | MR | Zbl

[5] Steger C., Ulrich M., Wiedemann C., Machine vision algorithms and applications, Cambridge University Press, New York, 2010

[6] Kaiser S., Biclustering: methods, software and application, Munchen, 2011

[7] Jain A. K., “Data clustering: 50 years beyond $k$-means”, Pattern Recognition Letters, 31 (2010), 651–666 | DOI

[8] Kelmanov A. V., Pyatkin A. V., “O slozhnosti odnogo iz variantov zadachi vybora podmnozhestva “pokhozhikh” vektorov”, Dokl. AN, 421:5 (2008), 590–592 | Zbl

[9] Gimadi E. Kh., Kelmanov A. V., Kelmanova M. A., Khamidullin S. A., “Aposteriornoe obnaruzhenie v chislovoi posledovatelnosti kvaziperiodicheskogo fragmenta pri zadannom chisle povtorov”, Sib. zh. industr. matematiki, 9:1(25) (2006), 55–74

[10] Gimadi E. Kh., Kel'manov A. V., Kel'manova M. A., Khamidullin S. A., “A Posteriori detecting a quasiperiodic fragment in a numerical sequence”, Pattern Recognition and Image Analysis, 18:1 (2008), 30–42 | DOI | MR

[11] Kelmanov A. V., “Problema off-line obnaruzheniya povtoryayuschegosya fragmenta v chislovoi posledovatelnosti”, Tr. In-t matem. i mekhan. UrO RAN, 14, no. 2, 2008, 81–88 | Zbl

[12] Dolgushev A. V., Kelmanov A. V., “Priblizhennyi algoritm resheniya odnoi zadachi klasternogo analiza”, Diskretnyi analiz i issledovanie operatsii, 18:2 (2011), 29–40

[13] Kelmanov A. V., Khandeev V. I., “Randomizirovannyi algoritm dlya odnoi zadachi dvukhklasternogo razbieniya mnozhestva vektorov”, Zh. vychisl. matem. i matem. fiz., 55:2 (2015), 335–344 | DOI | MR

[14] Aloise D., Deshpande A., Hansen P., Popat P., “NP-hardness of Euclidean sum-of-squares clustering”, Machine Learning, 75:2 (2009), 245–248 | DOI

[15] MacQueen J. B., “Some methods for classification and analysis of multivariate observations”, Proc. 5-th Berkeley Symp. of Mathematical Statistics and Probability, v. 1, Univ. of California Press, Berkeley, 1967, 281–297 | MR | Zbl

[16] Rao M., “Cluster analysis and mathematical programming”, J. Amer. Statist. Assoc., 66 (1971), 622–626 | DOI | Zbl

[17] Kelmanov A. V., Pyatkin A. V., “O slozhnosti nekotorykh zadach poiska podmnozhestv vektorov i klasternogo analiza”, Zh. vychisl. matem. i matem. fiz., 49:11 (2009), 2059–2065 | MR | Zbl

[18] Kelmanov A. V., “O slozhnosti nekotorykh zadach analiza dannykh”, Zh. vychisl. matem. i matem. fiz., 50:11 (2010), 2045–2051 | MR | Zbl

[19] Kelmanov A. V., “O slozhnosti nekotorykh zadach klasternogo analiza”, Zh. vychisl. matem. i matem. fiz., 51:11 (2011), 2106–2112 | MR | Zbl

[20] Baburin A. E., Gimadi E. X., Glebov N. I., Pyatkin A. V., “Zadacha otyskaniya podmnozhestva vektorov s maksimalnym summarnym vesom”, Diskretnyi analiz i issledovanie operatsii. Ser. 2, 14:1 (2007), 32–42 | Zbl

[21] Kelmanov A. V., Pyatkin A. V., “NP-polnota nekotorykh zadach vybora podmnozhestva vektorov”, Diskretnyi analiz i issledovanie operatsii, 17:5 (2010), 37–45 | Zbl

[22] Kelmanov A. V., Khandeev V. I., “Tochnyi psevdopolinomialnyi algoritm dlya odnoi zadachi dvukhklasternogo razbieniya mnozhestva vektorov”, Diskretnyi analiz i issledovanie operatsii, 22:4 (2015), 50–65

[23] Kelmanov A. V., Khandeev V. I., “Polinomialnyi algoritm s otsenkoi tochnosti 2 dlya resheniya odnoi zadachi klasternogo analiza”, Diskretnyi analiz i issledovanie operatsii, 20:4 (2013), 36–45 | MR

[24] Kelmanov A. V., Pyatkin A. V., “Ob odnom variante zadachi vybora podmnozhestva vektorov”, Diskretnyi analiz i issledovanie operatsii, 15:5 (2008), 20–34

[25] Garey M. R., Johnson D. S., Computers and intractability: a guide to the theory of NP-completeness, Freeman, San Francisco, 1979 | MR | Zbl

[26] Dolgushev A. V., Kelmanov A. V., Shenmaier V. V., “Polinomialnaya approksimatsionnaya skhema dlya odnoi zadachi razbieniya konechnogo mnozhestva na dva klastera”, Tr. Instituta matematiki i mekhaniki UrO RAN, 21, no. 3, 2015, 100–109

[27] Vazirani V. V., Approximation Algorithms, Springer, Berlin–Heidelberg–New York, 2001 | MR

[28] Kelmanov A. V., Romanchenko S. M., “FPTAS dlya odnoi zadachi poiska podmnozhestva vektorov”, Diskretnyi analiz i issledovanie operatsii, 21:3 (2014), 41–52 | MR

[29] Wirth I., Algorithms+data structures=programs, Prentice Hall, New Jersey, 1976 | MR | Zbl