Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2017, 11:4, 584-593
Volume 24, No 4, 2017, P. 111–129
UDC 519.16
V. V. Shenmaier
An exact algorithm for finding a vector subset with the longest sum
Abstract:
We consider the problem: Given a set of $n$ vectors in the $d$-dimensional Euclidean space, find a subset maximizing the length of the sum vector. We propose an algorithm that finds an optimal solution to this problem in time $O$($n^{d - 1}$ ($d$ + log $n$)). In particular, if the input vectors lie in a plane then the problem is solvable in almost linear time.
Illustr. 2, bibliogr. 14.
Keywords: sum vector, search for a vector subset, Euclidean space, polynomial-time algorithm, optimal solution.
DOI: 10.17377/daio.2017.24.541
Vladimir V. Shenmaier 1
1. Sobolev Institute of Mathematics,
4 Koptyug Ave., 630090 Novosibirsk, Russia
e-mail: shenmaier@mail.ru
Received 22 May 2016
Revised 10 May 2017
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 McGraw-Hill, 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).
