ENRU
English version: Journal of Applied and Industrial Mathematics, 2016, 10:3, 349–355 

Volume 23, No 3, 2016, P. 2134 UDC 519.16 + 519.85
Keywords: Euclidean space, balanced clustering, NPhardness, integer inputs, fixed space dimension, exact pseudopolynomial algorithm. DOI: 10.17377/daio.2016.23.520 Alexander V. Kel’manov ^{1,2} Received 25 May 2016 References[1] A. E. Baburin, E. Kh. Gimadi, N. I. Glebov, and A. V. Pyatkin, The problem of finding a subset of vectors with the maximum total weight, Diskretn. Anal. Issled. Oper., Ser. 2, 14, No. 1, 32–42, 2007. Translated inJ. Appl. Ind. Math., 2, No. 1, 32–38, 2008. [2] N. Wirth, Algorithms + Data Structures = Programs, Prentice Hall, Upper Saddle River, USA, 1976. Translated under the title Algoritmy + struktury dannykh = programmy, Mir, Moscow, 1985. [3] E. Kh. Gimadi, Yu. V. Glazkov, and 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, Diskretn. Anal. Issled. Oper., 15, No. 4, 30–43, 2008. Translated in J. Appl. Ind. Math., 3, No. 3, 343–352, 2009. [4] E. Kh. Gimadi, A. V. Kel’manov, M. A. Kel’manova, and S. A. Khamidullin, A posteriori detecting a quasiperiodic fragment with a given number of repetitions in a numerical sequence, Sib. Zh. Ind. Mat., 9, No. 1, 55–74, 2006. [5] A. V. Dolgushev and A. V. Kel’manov, An approximation algorithm for solving a problem of cluster analysis, Diskretn. Anal. Issled. Oper., 18, No. 2, 29–40, 2011. Translated in J. Appl. Ind. Math., 5, No. 4, 551–558, 2011. [6] A. V. Dolgushev, A. V. Kel’manov, and V. V. Shenmaier, Polynomialtime approximation scheme for a problem of partitioning a finite set into two clusters, Tr. Inst. Mat. Mekh., 21, No. 3, 100–109, 2015. [7] A. V. Kel’manov and A. V. Pyatkin, NPhardness of some quadratic Euclidean 2clustering problems, Dokl. Akad. Nauk, 464, No. 5, 535–538, 2015. Translated in Dokl. Math., 92, No. 2, 634–637, 2015. [8] A. V. Kel’manov and A. V. Pyatkin, On the complexity of some quadratic Euclidean 2clustering problems, Zh. Vychisl. Mat. Mat. Fiz., 56, No. 3, 150–156, 2016. Translated in Comput. Math. Math. Phys., 56, No. 3, 491–497, 2016. [9] A. V. Kel’manov and S. M. Romanchenko, Pseudopolynomial algorithms for certain computationally hard vector subset and cluster analysis problems, Avtom. Telemekh., No. 2, 156–162, 2012. Translated in Autom. Remote Control, 73, No. 2, 349–354, 2012. [10] A. V. Kel’manov and S. M. Romanchenko, An FPTAS for a vector subset search problem, Diskretn. Anal. Issled. Oper., 21, No. 3, 41–52, 2014. Translated in J. Appl. Ind. Math., 8, No. 3, 329–336, 2014. [11] A. V. Kel’manov and V. I. Khandeev, A 2approximation polynomial algorithm for a clustering problem, Diskretn. Anal. Issled. Oper., 20, No. 4, 36–45, 2013. Translated in J. Appl. Ind. Math., 7, No. 4, 515–521, 2013. [12] A. V. Kel’manov and V. I. Khandeev, A randomized algorithm for twocluster partition of a set of vectors, Zh. Vychisl. Mat. Mat. Fiz., 55, No. 2, 335–344, 2015. Translated in Comput. Math. Math. Phys., 55, No. 2, 330–339, 2015. [13] A. V. Kel’manov and V. I. Khandeev, An exact pseudopolynomial algorithm for a problem of the twocluster partitioning of a set of vectors, Diskretn. Anal. Issled. Oper., 22, No. 3, 36–48, 2015. Translated in J. Appl. Ind. Math., 9, No. 4, 497–502, 2015. [14] D. Aloise, A. Deshpande, P. Hansen, and P. Popat, NPhardness of Euclidean sumofsquares clustering, Mach. Learn., 75, No. 2, 245–248, 2009. [15] P. Brucker, On the complexity of clustering problems, in Optimization and Operations Research (Proc. Workshop Held Univ. Bonn, Bonn, Germany, Oct. 2–8, 1977), pp. 45–54, SpringerVerlag, Heidelberg, 1978 (Lect. Notes Econ. Math. Syst., Vol. 157). [16] W. F. de la Vega, M. Karpinski, C. Kenyon, and Y. Rabani, Polynomial time approximation schemes for metric MinSum clustering, in Electron. Colloq. Comput. Complexity, Report No. 25, HassoPlattnerInstitut Softwaresystemtechnik, Potsdam, 2002. [17] W. F. de la Vega and C. Kenyon, A randomized approximation scheme for metric MaxCut, J. Comput. Syst. Sci., 63, 531–541, 2001. [18] R. A. Fisher, Statistical methods and scientific inference, Hafner Press, New York, 1959. [19] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NPCompleteness, Freeman, San Francisco, 1979. Translated under the title Vychislitel’nye mashiny i trudnoreshaemye zadachi, Mir, Moscow, 1982. [20] E. Kh. Gimadi, A. V. Kel’manov, M. A. Kel’manova, and S. A. Khamidullin, A posteriori detecting a quasiperiodic fragment in a numerical sequence, Pattern Recognit. Image Anal., 18, No. 1, 30–42, 2008. [21] S. Hasegawa, H. Imai, M. Inaba, N. Katoh, and J. Nakano, Efficient algorithms for variancebased kclustering, in Computer Graphics and Applications (Proc. 1st Pac. Conf. Comput. Gr. Appl., Seoul, Korea, Aug. 30 – Sept. 2, 1993), pp. 75–89, World Scientific, River Edge, NJ, USA, 1993. [22] M. Inaba, N. Katoh, and H. Imai, Applications of weighted Voronoi diagrams and randomization to variancebased kclustering, in Proc. 10th Symp. Comput. Geom., Stony Brook, NY, USA, June 6–8, 1994, pp. 332–339, ACM, New York, 1994. [23] M. R. Rao, Cluster analysis and mathematical programming, J. Am. Stat. Assoc., 66, 622–626, 1971. [24] S. Sahni and T. Gonzalez, Pcomplete approximation problems, J. ACM, 23, 555–566, 1976. 

© Sobolev Institute of Mathematics, 2015  