Geodesic
On pseudopolynomial-time solvability of a quadratic Euclidean problem of finding a family of disjoint subsets
Sibirskij žurnal vyčislitelʹnoj matematiki, Tome 20 (2017) no. 1, pp. 15-22 
A. E. Galashov; A. V. Kel'manov. On pseudopolynomial-time solvability of a quadratic Euclidean problem of finding a family of disjoint subsets. Sibirskij žurnal vyčislitelʹnoj matematiki, Tome 20 (2017) no. 1, pp. 15-22. http://geodesic.mathdoc.fr/item/SJVM_2017_20_1_a1/
@article{SJVM_2017_20_1_a1,
     author = {A. E. Galashov and A. V. Kel'manov},
     title = {On pseudopolynomial-time solvability of a~quadratic {Euclidean} problem of finding a~family of disjoint subsets},
     journal = {Sibirskij \v{z}urnal vy\v{c}islitelʹnoj matematiki},
     pages = {15--22},
     year = {2017},
     volume = {20},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SJVM_2017_20_1_a1/}
}
TY  - JOUR
AU  - A. E. Galashov
AU  - A. V. Kel'manov
TI  - On pseudopolynomial-time solvability of a quadratic Euclidean problem of finding a family of disjoint subsets
JO  - Sibirskij žurnal vyčislitelʹnoj matematiki
PY  - 2017
SP  - 15
EP  - 22
VL  - 20
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/SJVM_2017_20_1_a1/
LA  - ru
ID  - SJVM_2017_20_1_a1
ER  - 
%0 Journal Article
%A A. E. Galashov
%A A. V. Kel'manov
%T On pseudopolynomial-time solvability of a quadratic Euclidean problem of finding a family of disjoint subsets
%J Sibirskij žurnal vyčislitelʹnoj matematiki
%D 2017
%P 15-22
%V 20
%N 1
%U http://geodesic.mathdoc.fr/item/SJVM_2017_20_1_a1/
%G ru
%F SJVM_2017_20_1_a1

Voir la notice de l'article provenant de la source Math-Net.Ru

We consider a strongly NP-hard problem of finding a family of disjoint subsets with given cardinalities in a finite set of points from the Euclidean space. A minimum of the sum over all required subsets of the sum of the squared distances from the elements of these subsets to their geometric centers is used as a search criterion. We have proved that if the coordinates of the input points are integer, and the space dimension and the number of required subsets are fixed (i.e. bounded by some constants), then the problem is a pseudopolynomial-time solvable one.

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

[2] Galashov A. E., Kelmanov A. V., “2-priblizhennyi algoritm dlya odnoi zadachi poiska semeistva neperesekayuschikhsya podmnozhestv vektorov”, Avtomatika i telemekhanika, 2014, no. 4, 5–19 | MR | Zbl

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

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

[5] Edwards A. W. F., Cavalli-Sforza L. L., “A method for cluster analysis”, Biometrics, 21 (1965), 362–375 | DOI

[6] MacQueen J. B., “Some methods for classification and analysis of multivariate observations”, Proc. 5th Berkeley Symp. Math. Statist. Probability, v. 1, 1967, 281–297 | MR | Zbl

[7] Garey M. R., Johnson D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979 | MR | Zbl

[8] Kelmanov A. V., Romanchenko S. M., “Priblizhennyi algoritm resheniya odnoi zadachi poiska podmnozhestva vektorov”, Diskretnyi analiz i issledovanie operatsii, 18:1 (2011), 61–69 | MR | Zbl

[9] Kelmanov A. V., Romanchenko S. M., “Psevdopolinomialnye algoritmy dlya nekotorykh trudnoreshaemykh zadach poiska podmnozhestva vektorov i klasternogo analiza”, Avtomatika i telemekhanika, 2012, no. 2, 156–162 | Zbl

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

[11] Shenmaier V. V., “Approksimatsionnaya skhema dlya odnoi zadachi poiska podmnozhestva vektorov”, Diskretnyi analiz i issledovanie operatsii, 19:2 (2012), 92–100 | MR | Zbl

[12] Papadimitriou C. H., Steiglitz K., Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, Englewood Cliffs, N.J., 1982 | MR | Zbl

[13] Mollin R. A., Fundamental Number Theory with Applications, Second Edition, CRC Press, 2008 | MR | Zbl