ENRU
English version: Journal of Applied and Industrial Mathematics, 2017, 11:4, 584593 

Volume 24, No 4, 2017, P. 111–129 UDC 519.16
Keywords: sum vector, search for a vector subset, Euclidean space, polynomialtime algorithm, optimal solution. DOI: 10.17377/daio.2017.24.541 Vladimir V. Shenmaier ^{1} Received 22 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 in J. Appl. Ind. Math., 2, No. 1, 32–38, 2008.[2] A. E. Baburin and A. V. Pyatkin, Polynomial algorithms for solving the vector sum problem, Diskretn. Anal. Issled. Oper., Ser. 1, 13, No. 2, 3–10, 2006. Translated in J. Appl. Ind. Math., 1, No. 3, 268–272, 2007. [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 detection of a quasiperiodic fragment with a given number of repetitions in a numerical sequence, Sib. Zh. Ind. Mat., 9, No. 1, 55–74, 2006. Translated in Pattern Recognit. Image Anal., 18, No. 1, 30–42, 2008. [5] 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. [6] A. V. Pyatkin, On complexity of a choice problem of the vector subset with the maximum sum length, Diskretn. Anal. Issled. Oper., 16, No. 6, 68–73, 2009. Translated in J. Appl. Ind. Math., 4, No. 4, 549–552, 2010. [7] V. V. Shenmaier, Solving some vector subset problems by Voronoi diagrams, Diskretn. Anal. Issled. Oper., 23, No. 4, 102–115, 2016. Translated in J. Appl. Ind. Math., 10, No. 4, 560–566, 2016. [8] R. C. Buck, Partition of space, Am. Math. Mon., 50, No. 9, 541–544, 1943. [9] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to algorithms, MIT Press and McGrawHill, Cambridge, MA, 2001. [10] H. Edelsbrunner, J. O’Rourke, and R. Seidel, Constructing arrangements of lines and hyperplanes with applications, SIAM J. Comput., 15, No. 2, 341–363, 1986. [11] F. K. Hwang, S. Onn, and U. G. Rothblum, A polynomial time algorithm for shaped partition problems, SIAM J. Optim., 10, No. 1, 70–81, 1999. [12] D. S. Johnson and F. P. Preparata, The densest hemisphere problem, Theor. Comp. Sci., 6, No. 1. [13] S. Onn and L. J. Schulman, The vector partition problem for convex objective functions, Math. Oper. Res., 26, No. 3, 583–590, 2001. [14] S. Onn (private communication, Nov. 2016). 

© Sobolev Institute of Mathematics, 2015  