Geodesic
A randomized algorithm for the vector subset problem with the maximal Euclidean norm of its sum
Diskretnyj analiz i issledovanie operacij, Tome 22 (2015) no. 3, pp. 5-17.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DA_2015_22_3_a0,
     author = {E. Kh. Gimadi and I. A. Rykov},
     title = {A randomized algorithm for the vector subset problem with the maximal {Euclidean} norm of its sum},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {5--17},
     publisher = {mathdoc},
     volume = {22},
     number = {3},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2015_22_3_a0/}
}
TY  - JOUR
AU  - E. Kh. Gimadi
AU  - I. A. Rykov
TI  - A randomized algorithm for the vector subset problem with the maximal Euclidean norm of its sum
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2015
SP  - 5
EP  - 17
VL  - 22
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2015_22_3_a0/
LA  - ru
ID  - DA_2015_22_3_a0
ER  - 
%0 Journal Article
%A E. Kh. Gimadi
%A I. A. Rykov
%T A randomized algorithm for the vector subset problem with the maximal Euclidean norm of its sum
%J Diskretnyj analiz i issledovanie operacij
%D 2015
%P 5-17
%V 22
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2015_22_3_a0/
%G ru
%F DA_2015_22_3_a0
E. Kh. Gimadi; I. A. Rykov. A randomized algorithm for the vector subset problem with the maximal Euclidean norm of its sum. Diskretnyj analiz i issledovanie operacij, Tome 22 (2015) no. 3, pp. 5-17. http://geodesic.mathdoc.fr/item/DA_2015_22_3_a0/

[1] A. V. Aho, J. E. Hopcroft, J. D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Boston, 1974 | MR | MR | Zbl

[2] A. E. Baburin, E. Kh. Gimadi, N. I. Glebov, A. V. Pyatkin, “The problem of finding a subset of vectors with the maximum total weight”, J. Appl. Ind. Math., 2:1 (2008), 32–38 | DOI | MR | Zbl

[3] E. Kh. Gimadi, N. I. Glebov, V. A. Perepelitsa, “Algorithms with estimates for discrete optimization problems”, Problems of Cybernetics, 31, ed. S. V. Yablonskii, Nauka, Moscow, 1976, 35–42

[4] E. Kh. Gimadi, A. V. Kel'manov, M. A. Kel'manova, 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:1 (2006), 55–74 | MR | Zbl

[5] E. Kh. Gimadi, A. V. Pyatkin, I. A. Rykov, “On polynomial solvability of some problems of a vector subset choice in a Euclidean space of fixed dimension”, J. Appl. Ind. Math., 4:1 (2010), 48–53 | DOI | MR | Zbl

[6] E. Kh. Gimadi, I. A. Rykov, “Approximation randomized algorithm for finding a vector subset with the maximal norm of sum in a Euclidean space”, Proc. Russian Conf. “Discrete Optimization and Operation Research” (Altay, Russia, June 27 – July 3, 2010), Izdatel'stvo Inst. Mat., Novosibirsk, 2010, 102

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

[8] A. V. Dolgushev, A. V. Kel'manov, “An approximation algorithm for solving a problem of cluster analysis”, J. Appl. Ind. Math., 5:4 (2011), 551–558 | DOI | MR | Zbl

[9] A. V. Dolgushev, A. V. Kel'manov, V. V. Shenmaier, “A polynomial approximation scheme for a problem of cluster analysis”, Proc. 9th Int. Conf. “Intellectualization of Information Processing” (Budva, Montenegro, Sept. 16–22, 2012), Torus Press, Moscow, 2012, 242–244

[10] A. V. Kel'manov, V. I. Khandeev, “A randomized algorithm for two-cluster partition of a set of vectors”, Comput. Math. Math. Phys., 55:2 (2015), 330–339 | DOI | DOI | MR | Zbl

[11] Bern M., Eppstein D., “Approximation algorithms for geometric problems”, Approximation algorithms for NP-hard problems, PWS Publ. Co., Boston, 1997, 296–345

[12] Bishop C. M., Pattern recognition and machine learning, Springer, New York, 2006, 738 pp. | MR | Zbl

[13] James G., Witten D., Hastie T., Tibshirani R., An introduction to statistical learning, Springer, New York, 2013, 426 pp. | MR | Zbl

[14] Jain A. K., “Data clustering: 50 years beyond $K$-means”, Pattern. Recognit. Lett., 31 (2010), 651–666 | DOI

[15] Flach P., Machine learning: The art and science of algorithms that make sense of data, Cambridge Univ. Press, New York, 2012, 396 pp. | MR | Zbl

[16] Huber G., “Notes: gamma function derivation of $n$-sphere volumes”, Amer. Math. Monthly, 89:5 (1982), 301–302 | DOI | MR

[17] MacQueen J. B., “Some methods for classification and analysis of multivariate observations”, Proc. 5th Berkeley Symp. Math. Stat. Probab., v. 1, Univ. California Press, Berkeley, CA, 1967, 281–297 | MR | Zbl

[18] Rao M. R., “Cluster analysis and mathematical programming”, J. Amer. Stat. Assoc., 66 (1971), 622–626 | DOI | Zbl