Geodesic
Exact pseudopolinomial algorithms for a~balanced $2$-clustering problem
Diskretnyj analiz i issledovanie operacij, Tome 23 (2016) no. 3, pp. 21-34.

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

We consider the strongly NP-hard problem of partitioning a set of Euclidean points into two clusters so as to minimize the sum (over both clusters) of the weighted sum of the squared intracluster distances from the elements of the clusters to their centers. The weights of sums are the sizes of the clusters. The center of one cluster is given as input, while the center of the other cluster is unknown and determined as the average value over all points in the cluster (the geometric center). The two versions of the problems are analyzed in which the cluster sizes are either parts of the input or optimization variables. We present and prove exact pseudopolynomial algorithms in the case of integer components of the input points and fixed space dimension. Bibliogr. 24.
Keywords: Euclidean space, balanced clustering, NP-hardness, integer inputs, fixed space dimension
Mots-clés : exact pseudopolynomial algorithm. 
@article{DA_2016_23_3_a1,
     author = {A. V. Kel'manov and A. V. Motkova},
     title = {Exact pseudopolinomial algorithms for a~balanced $2$-clustering problem},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {21--34},
     publisher = {mathdoc},
     volume = {23},
     number = {3},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2016_23_3_a1/}
}
TY  - JOUR
AU  - A. V. Kel'manov
AU  - A. V. Motkova
TI  - Exact pseudopolinomial algorithms for a~balanced $2$-clustering problem
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2016
SP  - 21
EP  - 34
VL  - 23
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2016_23_3_a1/
LA  - ru
ID  - DA_2016_23_3_a1
ER  - 
%0 Journal Article
%A A. V. Kel'manov
%A A. V. Motkova
%T Exact pseudopolinomial algorithms for a~balanced $2$-clustering problem
%J Diskretnyj analiz i issledovanie operacij
%D 2016
%P 21-34
%V 23
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2016_23_3_a1/
%G ru
%F DA_2016_23_3_a1
A. V. Kel'manov; A. V. Motkova. Exact pseudopolinomial algorithms for a~balanced $2$-clustering problem. Diskretnyj analiz i issledovanie operacij, Tome 23 (2016) no. 3, pp. 21-34. http://geodesic.mathdoc.fr/item/DA_2016_23_3_a1/

[1] A. E. Baburin, E. Kh. Gimadi, N. I. Glebov, A. V. Pyatkin, “The problem of finding a subset of vectors with the maximum total weight”, J. Appl. Ind. Math., 2:1 (2008), 32–38 | DOI | MR | Zbl

[2] N. Wirth, Algorithms + Data Structures = Programs, Prentice Hall, Upper Saddle River, USA, 1976 | MR | Zbl

[3] E. Kh. Gimadi, Yu. V. Glazkov, I. A. Rykov, “On two problems of choosing some subset of vectors with integer coordinates that has maximum norm of the sum of elements in Euclidean space”, J. Appl. Ind. Math., 3:3 (2009), 343–352 | DOI | MR | Zbl

[4] E. Kh. Gimadi, A. V. Kel'manov, M. A. Kel'manova, S. A. Khamidullin, “A posteriori detecting a quasiperiodic fragment with a given number of repetitions in a numerical sequence”, Sib. Zh. Ind. Mat., 9:1 (2006), 55–74 | MR | Zbl

[5] A. V. Dolgushev, A. V. Kel'manov, “An approximation algorithm for solving a problem of cluster analysis”, J. Appl. Ind. Math., 5:4 (2011), 551–558 | DOI | MR | Zbl

[6] A. V. Dolgushev, A. V. Kel'manov, V. V. Shenmaier, “Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters”, Tr. Inst. Mat. Mekh., 21, no. 3, 2015, 100–109 | MR

[7] A. V. Kel'manov, A. V. Pyatkin, “NP-hardness of some quadratic Euclidean 2-clustering problems”, Dokl. Math., 92:2 (2015), 634–637 | DOI | DOI | MR | Zbl

[8] A. V. Kel'manov, A. V. Pyatkin, “On the complexity of some quadratic Euclidean 2-clustering problems”, Comput. Math. Math. Phys., 56:3 (2016), 491–497 | DOI | DOI | MR | Zbl

[9] A. V. Kel'manov, S. M. Romanchenko, “Pseudopolynomial algorithms for certain computationally hard vector subset and cluster analysis problems”, Autom. Remote Control, 73:2 (2012), 349–354 | DOI | MR | Zbl

[10] A. V. Kel'manov, S. M. Romanchenko, “An FPTAS for a vector subset search problem”, J. Appl. Ind. Math., 8:3 (2014), 329–336 | DOI | MR | Zbl

[11] A. V. Kel'manov, V. I. Khandeev, “A 2-approximation polynomial algorithm for a clustering problem”, J. Appl. Ind. Math., 7:4 (2013), 515–521 | DOI | MR | Zbl

[12] A. V. Kel'manov, V. I. Khandeev, “A randomized algorithm for two-cluster partition of a set of vectors”, Comput. Math. Math. Phys., 55:2 (2015), 330–339 | DOI | DOI | MR | Zbl

[13] A. V. Kel'manov, V. I. Khandeev, “An exact pseudopolynomial algorithm for a problem of the two-cluster partitioning of a set of vectors”, J. Appl. Ind. Math., 9:4 (2015), 497–502 | DOI | DOI | MR | Zbl

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

[15] Brucker P., “On the complexity of clustering problems”, Optimization and Operations Research, Proc. Workshop Held Univ. Bonn (Bonn, Germany, Oct. 2–8, 1977), Lect. Notes Econom. Math. Systems, 157, Springer-Verl., Heidelberg, 1978, 45–54 | DOI | MR

[16] De la Vega W. F., Karpinski M., Kenyon C., Rabani Y., Polynomial time approximation schemes for metric min-sum clustering, Electron. Colloq. Comput. Complexity (ECCC), Report No. 25, Hasso-Plattner-Inst. Softwaresystemtechnik, Potsdam, 2002

[17] De la Vega W. F., Kenyon C., “A randomized approximation scheme for metric Max-Cut”, J. Comput. Syst. Sci., 63 (2001), 531–541 | DOI | MR | Zbl

[18] Fisher R. A., Statistical methods and scientific inference, Hafner Press, New York, 1959, 350 pp. | MR

[19] Garey M. R., Johnson D. S., Computers and intractability: a guide to the theory of NP-completeness, Freeman, San Francisco, 1979, 314 pp. ; M. Geri, D. Dzhonson, Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982 | MR | Zbl | MR

[20] 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 Recognit. Image Anal., 18:1 (2008), 30–42 | DOI | MR

[21] Hasegawa S., Imai H., Inaba M., Katoh N., Nakano J., “Efficient algorithms for variance-based $k$-clustering”, Proc. 1st Pac. Conf. Comput. Graphics Appl. (Seoul, Korea, Aug. 30 – Sept. 2, 1993), v. 1, World Scientific, River Edge, NJ, 1993, 75–89

[22] Inaba M., Katoh N., Imai H., “Applications of weighted Voronoi diagrams and randomization to variance-based $k$-clustering”, Proc. 10th Symp. Comput. Geom. (Stony Brook, NY, USA, June 6–8, 1994), ACM, New York, 1994, 332–339

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

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