RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor
Subscription

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Diskretn. Anal. Issled. Oper.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Diskretn. Anal. Issled. Oper., 2015, Volume 22, Number 3, Pages 5–17 (Mi da816)  

This article is cited in 2 scientific papers (total in 2 papers)

A randomized algorithm for the vector subset problem with the maximal Euclidean norm of its sum

E. Kh. Gimadia, I. A. Rykovb

a Sobolev Institute of Mathematics, 4 Koptyug Ave., 630090 Novosibirsk, Russia
b Novosibirsk State University, 2 Pirogov St., 630090 Novosibirsk, Russia

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: https://doi.org/10.17377/daio.2015.22.465

Full text: PDF file (290 kB)
References: PDF file   HTML file

English version:
Journal of Applied and Industrial Mathematics, 2015, 9:3, 351–357

Bibliographic databases:

UDC: 519.174
Received: 21.10.2014
Revised: 02.03.2015

Citation: E. Kh. Gimadi, I. A. Rykov, “A randomized algorithm for the vector subset problem with the maximal Euclidean norm of its sum”, Diskretn. Anal. Issled. Oper., 22:3 (2015), 5–17; J. Appl. Industr. Math., 9:3 (2015), 351–357

Citation in format AMSBIB
\Bibitem{GimRyk15}
\by E.~Kh.~Gimadi, I.~A.~Rykov
\paper A randomized algorithm for the vector subset problem with the maximal Euclidean norm of its sum
\jour Diskretn. Anal. Issled. Oper.
\yr 2015
\vol 22
\issue 3
\pages 5--17
\mathnet{http://mi.mathnet.ru/da816}
\crossref{https://doi.org/10.17377/daio.2015.22.465}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3443295}
\elib{http://elibrary.ru/item.asp?id=23859889}
\transl
\jour J. Appl. Industr. Math.
\yr 2015
\vol 9
\issue 3
\pages 351--357
\crossref{https://doi.org/10.1134/S1990478915030060}


Linking options:
  • http://mi.mathnet.ru/eng/da816
  • http://mi.mathnet.ru/eng/da/v22/i3/p5

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. A. Kel'manov, V. Khandeev, “Some algorithms with guaranteed accuracy for 2-clustering problems with given center of one cluster”, 2017 International Multi-Conference on Engineering, Computer and Information Sciences (SIBIRCON), IEEE, 2017, 91–93  crossref  isi
    2. A. V. Eremeev, A. V. Kel'manov, A. V. Pyatkin, “On complexity of searching a subset of vectors with shortest average under a cardinality restriction”, Analysis of Images, Social Networks and Texts, AIST 2016, Communications in Computer and Information Science, 661, ed. D. Ignatov, M. Khachay, V. Labunets, N. Loukachevitch, S. Nikolenko, A. Panchenko, A. Savchenko, K. Vorontsov, Springler, 2017, 51–57  crossref  mathscinet  isi  scopus
  • Дискретный анализ и исследование операций
    Number of views:
    This page:173
    Full text:29
    References:36
    First page:13

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2019