Geodesic
On the complexity of some quadratic Euclidean 2-clustering problems
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 56 (2016) no. 3, pp. 498-504 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Some problems of partitioning a finite set of points of Euclidean space into two clusters are considered. In these problems, the following criteria are minimized: (1) the sum over both clusters of the sums of squared pairwise distances between the elements of the cluster and (2) the sum of the (multiplied by the cardinalities of the clusters) sums of squared distances from the elements of the cluster to its geometric center, where the geometric center (or centroid) of a cluster is defined as the mean value of the elements in that cluster. Additionally, another problem close to (2) is considered, where the desired center of one of the clusters is given as input, while the center of the other cluster is unknown (is the variable to be optimized) as in problem (2). Two variants of the problems are analyzed, in which the cardinalities of the clusters are (1) parts of the input or (2) optimization variables. It is proved that all the considered problems are strongly NP-hard and that, in general, there is no fully polynomial-time approximation scheme for them (unless P = NP). 
@article{ZVMMF_2016_56_3_a16,
     author = {A. V. Kel'manov and A. V. Pyatkin},
     title = {On the complexity of some quadratic {Euclidean} 2-clustering problems},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {498--504},
     year = {2016},
     volume = {56},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2016_56_3_a16/}
}
TY  - JOUR
AU  - A. V. Kel'manov
AU  - A. V. Pyatkin
TI  - On the complexity of some quadratic Euclidean 2-clustering problems
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2016
SP  - 498
EP  - 504
VL  - 56
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2016_56_3_a16/
LA  - ru
ID  - ZVMMF_2016_56_3_a16
ER  - 
%0 Journal Article
%A A. V. Kel'manov
%A A. V. Pyatkin
%T On the complexity of some quadratic Euclidean 2-clustering problems
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2016
%P 498-504
%V 56
%N 3
%U http://geodesic.mathdoc.fr/item/ZVMMF_2016_56_3_a16/
%G ru
%F ZVMMF_2016_56_3_a16
A. V. Kel'manov; A. V. Pyatkin. On the complexity of some quadratic Euclidean 2-clustering problems. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 56 (2016) no. 3, pp. 498-504. http://geodesic.mathdoc.fr/item/ZVMMF_2016_56_3_a16/

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

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

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

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

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

[6] Sahni S., Gonzalez T., “P-complete approximation problems”, J. of the ACM, 23 (1976), 555–566 | DOI | MR

[7] Brucker P., “On the complexity of clustering problems”, Lecture Notes in Economics and Mathematical Systems, 157, 1978, 45–54 | DOI | MR | Zbl

[8] de la Vega F., Kenyon C., “A randomized approximation scheme for metric max-cut”, J. Comput. and Sci., 63 (2001), 531–541 | MR | Zbl

[9] de la Vega F., Karpinski M., Kenyon C., Rabani Y., Polynomial time approximation schemes for Metric min-sum clustering, Electronic Colloquium on Computational Complexity (ECCC), Report No 25, 2002

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

[11] 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

[12] Fisher R. A., Statistical methods and scientific inference, Hafner Press, New York, 1956

[13] Galashov A. E., Kelmanov A. V., “2-priblizhennyi algoritm dlya odnoi zadachi poiska semeistva neperesekayuschikhsya podmnozhestv vektorov”, Avtomatika i telemekhanika, 4 (2014), 5–17

[14] Inaba M., Katoh N., Imai H., “Applications of weighted Voronoi diagrams and randomization to variance-based k-clustering: (extended abstract)”, Proc. 10th ACM Symposium on Computational Geometry (Strony Brook, New York, 1994), 1994, 332–339

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

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

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

[18] Ageev A. A., Kelmanov A. V., Pyatkin A. V., “Trudnoreshaemost zadachi o razreze maksimalnogo vesa v evklidovom prostranstve”, Dokl. AN, 456:5 (2014), 511–513 | DOI | Zbl

[19] Ageev A. A., Kelmanov A. V., Pyatkin A. V., “Slozhnost zadachi o razreze maksimalnogo vesa v evklidovom prostranstve”, Diskretnyi analiz i issledovanie operatsii, 21:4 (2014), 3–11

[20] Bui T. N., Chaudhuri S., Leighton F. T., Sipser M., “Graph bisection algorithms with good average case behavior”, Combinatorica, 7:2 (1987), 171–191 | DOI | MR

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