Diskretnyi Analiz i Issledovanie Operatsii
General information
Latest issue
Impact factor
Guidelines for authors

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Diskretn. Anal. Issled. Oper.:

Personal entry:
Save password
Forgotten password?

Diskretn. Anal. Issled. Oper., 2008, Volume 15, Issue 4, Pages 30–43 (Mi da539)  

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

The vector subset problem with integer coordinates in Euclidean space with the maximum sum

E. Kh. Gimadi, Yu. V. Glazkov, I. A. Rykov

Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences

Abstract: Two problems of selecting a subset of $m$ vectors with the maximum norm of sum from a set of $n$ vectors in Euclidean space $\mathbb R^k$ is considered. It is supposed that the coordinates of the vectors are integer. Using the dynamic programming technique new optimal algorithms are constructed. They have pseudopolynomial complexity, when the dimension $k$ of the vector space is fixed. New algorithms have certain advantages (with respect to earlier known algorithms): the vector subset problem can be solved faster, if $m<(k/2)^k$, and the time complexity is $k^{k-1}$ times less for the problem with an additional restriction on the order of vectors independently of $m$. Bibl. 5.

Keywords: subset selection, Euclidian metric, time complexity, pseudopolynomial algorithm, dynamic programming.

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

English version:
Journal of Applied and Industrial Mathematics, 2009, 3:3, 343–352

Bibliographic databases:

UDC: 519.8
Received: 16.03.2008
Revised: 20.06.2008

Citation: E. Kh. Gimadi, Yu. V. Glazkov, I. A. Rykov, “The vector subset problem with integer coordinates in Euclidean space with the maximum sum”, Diskretn. Anal. Issled. Oper., 15:4 (2008), 30–43; J. Appl. Industr. Math., 3:3 (2009), 343–352

Citation in format AMSBIB
\by E.~Kh.~Gimadi, Yu.~V.~Glazkov, I.~A.~Rykov
\paper The vector subset problem with integer coordinates in Euclidean space with the maximum sum
\jour Diskretn. Anal. Issled. Oper.
\yr 2008
\vol 15
\issue 4
\pages 30--43
\jour J. Appl. Industr. Math.
\yr 2009
\vol 3
\issue 3
\pages 343--352

Linking options:
  • http://mi.mathnet.ru/eng/da539
  • http://mi.mathnet.ru/eng/da/v15/i4/p30

    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. E. Kh. Gimadi, A. V. Pyatkin, I. A. Rykov, “On polynomial solvability of some vector subset problems in Euclidean space with fixed dimension”, J. Appl. Industr. Math., 4:1 (2010), 48–53  mathnet  crossref  mathscinet  zmath
    2. A. V. Dolgushev, A. V. Kel'manov, “An approximation algorithm for one problem of cluster analysis”, J. Appl. Industr. Math., 5:4 (2011), 551–558  mathnet  crossref  mathscinet  zmath
    3. A. V. Kel'manov, V. I. Khandeev, “An exact pseudopolynomial algorithm for a bi-partitioning problem”, J. Appl. Industr. Math., 9:4 (2015), 497–502  mathnet  crossref  crossref  mathscinet  elib
    4. A. V. Dolgushev, A. V. Kel'manov, V. V. Shenmaier, “Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters”, Proc. Steklov Inst. Math. (Suppl.), 295, suppl. 1 (2016), 47–56  mathnet  crossref  mathscinet  isi  elib
    5. A. V. Kel'manov, S. A. Khamidullin, V. I. Khandeev, “Fully polynomial-time approximation scheme for a sequence $2$-clustering problem”, J. Appl. Industr. Math., 10:2 (2016), 209–219  mathnet  crossref  crossref  mathscinet  elib
    6. A. V. Kel'manov, A. V. Motkova, “Exact pseudopolinomial algorithms for a balanced $2$-clustering problem”, J. Appl. Industr. Math., 10:3 (2016), 349–355  mathnet  crossref  crossref  mathscinet  elib
    7. A. V. Eremeev, A. V. Kel'manov, A. V. Pyatkin, “On the complexity and approximability of some Euclidean optimal summing problems”, Comput. Math. Math. Phys., 56:10 (2016), 1813–1817  mathnet  crossref  crossref  isi  elib
    8. A. V. Kel'manov, A. V. Motkova, V. V. Shenmaier, “Approximation scheme for the problem of weighted 2-partitioning with a fixed center of one cluster”, Proc. Steklov Inst. Math. (Suppl.), 303, suppl. 1 (2018), 136–145  mathnet  crossref  crossref  isi  elib
    9. V. V. Shenmaier, “An exact algorithm for finding a vector subset with the longest sum”, J. Appl. Industr. Math., 11:4 (2017), 584–593  mathnet  crossref  crossref  elib
    10. Kel'manov A. Khandeev V., “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
    11. Eremeev A.V. Kel'manov A.V. Pyatkin A.V., “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. Ignatov D. Khachay M. Labunets V. Loukachevitch N. Nikolenko S. Panchenko A. Savchenko A. Vorontsov K., Springer International Publishing Ag, 2017, 51–57  crossref  isi  scopus
  • Дискретный анализ и исследование операций
    Number of views:
    This page:513
    Full text:113
    First page:11

    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021