Volume 22, No 3, 2015, P. 5-17

UDC 519.174
Gimadi E. Kh., Rykov I. A. 
A randomized algorithm for the vector subset problem with the maximal Euclidean norm of its sum

Abstract:
We present a randomized approximation algorithm for the problem of finding a subset of a finite set of vectors in the Euclidean space with the maximal norm of the sum vector. We show that with an appropriate choice of parameters, the algorithm is polynomial for the problem with any fixed dimension and asymptotically optimal.
Il. 1, bibliogr. 18.

Keywords: search for vector subset, randomized algorithm, asymptotical exactness.

DOI: 10.17377/daio.2015.22.465

Edward Kh. Gimadi ^1,2
Ivan A. Rykov ¹
1. Sobolev Institute of Mathematics,
4 Koptyug Ave., 630090 Novosibirsk, Russia
2. Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: gimadi@math.nsc.ru, rykovweb@gmail.com

Received 21 October 2014
Revised 2 March 2015

References

[1] A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Boston, 1974. Translated under the title Postroenie i analiz vychislitel’nykh algoritmov, Mir, Moscow, 1979.

[2] 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.

[3] E. Kh. Gimadi, N. I. Glebov, and V. A. Perepelitsa, Algorithms with estimates for discrete optimization problems, in S. V. Yablonskii, ed., Problemy kibernetiki (Problems of Cybernetics), Vol. 31, pp. 35–42, Nauka, Moscow, 1976.

[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.

[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] E. Kh. Gimadi and I. A. Rykov, Approximation randomized algorithm for finding a vector subset with the maximal norm of sum in a Euclidean space, in Materialy Rossiiskoi konferentsii “Diskretnaya optimizatsiya i issledovanie operatsii” (Proc. Russian Conf. “Discrete Optimization and Operation Research”), Altay, Russia, June 27 – July 3, 2010, p. 102, Izdatel’stvo Inst. Mat., Novosibirsk, 2010.

[7] E. Kh. Gimadi and I. A. Rykov, Randomized algorithm for finding a vector subset with the maximal norm of sum in a Euclidean space, in Trudy XV Baikal’skoi mezhdunarodnoi shkoly-seminara “Metody optimizatsii i ikh prilozheniya” (Proc. XV Baikal Int. School-Seminar “Optimization Methods and Their Applications”), Listvyanka, Irkutsk Reg., Russia, June 23–29, 2011, Vol. 4, pp. 76–81, RIO IDSTU SO RAN, Irkutsk, 2011.

[8] 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.

[9] A. V. Dolgushev, A. V. Kel’manov, and V. V. Shenmaier, A polynomial approximation scheme for a problem of cluster analysis, in Doklady 9 mezhdunarodnoi konferentsii “Intellektualizatsiya obrabotki informatsii” (Proc. 9th Int. Conf. “Intellectualization of Information Processing”), Budva, Montenegro, Sept. 16–22, 2012, pp. 242–244, Torus Press, Moscow, 2012.

[10] A. V. Kel’manov and V. I. Khandeev, A randomized algorithm for two-cluster 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.

[11] M. Bern and D. Eppstein, Approximation algorithms for geometric problems, in D. S. Hochbaum, ed., Approximation Algorithms for NP-hard Problems, pp. 296–345, PWS Publ. Co., Boston, 1997.

[12] C. M. Bishop, Pattern Recognition and Machine Learning, Springer, New York, 2006.

[13] G. James, D. Witten, T. Hastie, and D. Tibshirani, An Introduction to Statistical Learning. With Applications in R, Springer, New York, 2013.

[14] A. K. Jain, Data clustering: 50 years beyond K-means, Pattern Recognit. Lett., 31, No. 8, 651–666, 2010.

[15] P. Flach, Machine Learning. The Art and Science of Algorithms that Make Sense of Data, Cambridge Univ. Press, Cambridge, 2012.

[16] G. Huber, Gamma function derivation of n-sphere volumes, Am. Math. Mon., 89, No. 5, 301–302, 1982.

[17] J. B. MacQueen, Some methods for classification and analysis of multivariate observations, in L. M. Le Cam and J. Neyman, eds., Proc. 5th Berkeley Symp. Math. Stat. Probab., Berkeley, USA, June 21 – July 18, 1965 and Dec. 27, 1965 – Jan. 7, 1966, Vol. 1, pp. 281–297, Univ. of California Press, Berkeley, 1967.

[18] M. R. Rao, Cluster analysis and mathematical programming, J. Am. Stat. Assoc., 66, 622–626, 1971.