ENRU
English version: Journal of Applied and Industrial Mathematics, 2016, 10:2, 209219 

Volume 23, No 2, 2016, P. 2140 UDC 519.16+519.85
Keywords: partitioning, sequence, Euclidean space, minimum sumofsquared distances, NPhardness, FPTAS. DOI: 10.17377/daio.2016.23.511 Alexander V. Kel’manov ^{1,2} Received 15 September 2015 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] 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. [3] E. Kh. Gimadi, A. V. Pyatkin, and I. A. Rykov, On polynomial solvability of some problems of a vector subset choice in a Euclidean space of fixed dimension, Diskretn. Anal. Issled. Oper., 15, No. 6, 11–19, 2008. Translated in J. Appl. Ind. Math., 4, No. 1, 48–53, 2010. [4] 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. [5] 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. [6] A. V. Kel’manov, Offline detection of a quasiperiodically recurring fragment in a numerical sequence, Tr. Inst. Mat. Mekh., 14, No. 2, 81–88, 2008. Translated in Proc. Steklov Inst. Math., 263, Suppl. 2, S84–S92, 2008. [7] A. V. Kel’manov, On the complexity of some data analysis problems, Zh. Vychisl. Mat. Mat. Fiz., 50, No. 11, 2045–2051, 2010. Translated in Comput. Math. Math. Phys., 50, No. 11, 1941–1947, 2010. [8] A. V. Kel’manov, On the complexity of some cluster analysis problems, Zh. Vychisl. Mat. Mat. Fiz., 51, No. 11, 2106–2112, 2011. Translated in Comput. Math. Math. Phys., 51, No. 11, 1983–1988, 2011. [9] A. V. Kel’manov and A. V. Pyatkin, Complexity of certain problems of searching for subsets of vectors and cluster analysis, Zh. Vychisl. Mat. Mat. Fiz., 49, No. 11, 2059–2067, 2009. Translated in Comput. Math. Math. Phys., 49, No. 11, 1966–1971, 2009. [10] A. V. Kel’manov and A. V. Pyatkin, On complexity of some problems of cluster analysis of vector sequences, Diskretn. Anal. Issled. Oper., 20, No. 2, 47–57, 2013. Translated in J. Appl. Ind. Math., 7, No. 3, 363–369, 2013. [11] 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. [12] A. V. Kel’manov and S. A. Khamidullin, Posterior detection of a given number of identical subsequences in a quasiperiodic sequence, Zh. Vychisl. Mat. Mat. Fiz., 41, No. 5, 807–820, 2001. Translated in Comput. Math. Math. Phys., 41, No. 5, 762–774, 2001. [13] A. V. Kel’manov and S. A. Khamidullin, An approximating polynomial algorithm for a sequence partitioning problem, Diskretn. Anal. Issled. Oper., 21, No. 1, 53–66, 2014. Translated in J. Appl. Ind. Math., 8, No. 2, 236–244, 2014. [14] A. V. Kel’manov and S. A. Khamidullin, An approximation polynomialtime algorithm for a sequence biclustering problem, Zh. Vychisl. Mat. Mat. Fiz., 55, No. 6, 1076–1085, 2015. Translated in Comput. Math. Math. Phys., 55, No. 6, 1068–1076, 2015. [15] A. V. Kel’manov, S. A. Khamidullin, and V. I. Khandeev, An exact pseudopolynomial algorithm for a sequence biclustering problem, in Tezisy dokladov XV Vserossiiskoy konferentsii “Matematicheskoe programmirovanie i prilozheniya” (Abstr. XV AllRuss. Conf. “Mathematical Programming and Applications”), Ekaterinburg, Russia, Mar. 2–6, 2015, pp. 139–140, Inst. Mat. Mekh. UrO RAN, Ekaterinburg, 2015. [16] 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. [17] 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. [18] A. V. Kel’manov and V. I. Khandeev, Fully polynomialtime approximation scheme for special case of a quadratic Euclidean 2clustering problem, Zh. Vychisl. Mat. Mat. Fiz., 56, No. 2, 145–153, 2016. [19] D. Aloise, A. Deshpande, P. Hansen, and P. Popat, NPhardness of Euclidean sumofsquares clustering, Mach. Learn., 75, No. 2, 245–248, 2009. [20] C. M. Bishop, Pattern Recognition and Machine Learning, Springer, New York, 2006. [21] J. A. Carter [et al.], Kepler36: A pair of planets with neighboring orbits and dissimilar densities, Science, 337, No. 6094, 556–559, 2012. [22] P. Flach, Machine Learning: The Art and Science of Algorithms that Make Sense of Data, Cambridge Univ. Press, New York, 2012. [23] 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. [24] A. K. Jain, Data clustering: 50 years beyond Kmeans, Pattern Recognit. Lett., 31, No. 8, 651–666, 2010. [25] G. James, D. Witten, T. Hastie, and D. Tibshirani, An Introduction to Statistical Learning: With Applications in R, Springer, New York, 2013. [26] A. V. Kel’manov and B. Jeon, A posteriori joint detection and discrimination of pulses in a quasiperiodic pulse train, IEEE Trans. Signal Process., 52, No. 3, 645–656, 2004. [27] C. Steger, M. Ulrich, and C. Wiedemann, Machine Vision Algorithms and Applications, WileyVCH, Berlin, 2007. 

© Sobolev Institute of Mathematics, 2015  