General information
Latest issue
Impact factor

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, Number 5, Pages 20–34 (Mi da547)  

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

On one variant of the vectors subset choice problem

A. V. Kel'manov, A. V. Pyatkin

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

Abstract: One variant of the problem of a posteriori (off-line) noise proof search for the unknown repeating vector in the case, when the noise is additive, can be reduced to the “similar” vectors subset choice problem. This problem is proved to be NP-complete. A polynomial approximation algorithm with guaranteed relative error bounds in the case of the fixed dimension of the space is suggested for this problem. Bibl. 13.

Keywords: numerical vector sequence, a posteriori processing, repeating vector, optimal noise proof detecting, complexity, NP-completeness, approximation algorithm.

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

English version:
Journal of Applied and Industrial Mathematics, 2009, 3:4, 447–455

Bibliographic databases:

UDC: 519.2+621.391
Received: 01.04.2008

Citation: A. V. Kel'manov, A. V. Pyatkin, “On one variant of the vectors subset choice problem”, Diskretn. Anal. Issled. Oper., 15:5 (2008), 20–34; J. Appl. Industr. Math., 3:4 (2009), 447–455

Citation in format AMSBIB
\by A.~V.~Kel'manov, A.~V.~Pyatkin
\paper On one variant of the vectors subset choice problem
\jour Diskretn. Anal. Issled. Oper.
\yr 2008
\vol 15
\issue 5
\pages 20--34
\jour J. Appl. Industr. Math.
\yr 2009
\vol 3
\issue 4
\pages 447--455

Linking options:

    SHARE: FaceBook Twitter Livejournal

    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. Pyatkin, “On the complexity of the maximum sum length vectors subset choice problem”, J. Appl. Industr. Math., 4:4 (2010), 549–552  mathnet  crossref  mathscinet  zmath  elib
    3. A. V. Kel'manov, A. V. Pyatkin, “Complexity of certain problems of searching for subsets of vectors and cluster analysis”, Comput. Math. Math. Phys., 49:11 (2009), 1966–1971  mathnet  crossref  mathscinet  isi
    4. A. V. Kel'manov, A. V. Pyatkin, “NP-completeness of some problems of a vectors subset choice”, J. Appl. Industr. Math., 5:3 (2011), 352–357  mathnet  crossref  mathscinet  zmath
    5. A. V. Kelmanov, “$NP$-polnota nekotorykh zadach poiska podmnozhestv vektorov”, Tr. IMM UrO RAN, 16, no. 3, 2010, 121–129  mathnet  elib
    6. A. V. Kel'manov, “On the complexity of some data analysis problems”, Comput. Math. Math. Phys., 50:11 (2010), 1941–1947  mathnet  crossref  adsnasa  isi
    7. A. V. Kel'manov, “On the complexity of some cluster analysis problems”, Comput. Math. Math. Phys., 51:11 (2011), 1983–1988  mathnet  crossref  mathscinet  isi
    8. A. V. Kel'manov, A. V. Pyatkin, “On the complexity of some vector sequence clustering problems”, J. Appl. Industr. Math., 7:3 (2013), 363–369  mathnet  crossref  mathscinet
    9. A. V. Kelmanov, V. I. Khandeev, “A $2$-approximation polynomial algorithm for one clustering problem”, J. Appl. Industr. Math., 7:4 (2013), 515–521  mathnet  crossref  mathscinet
    10. 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
    11. A. V. Kel'manov, V. I. Khandeev, “Fully polynomial-time approximation scheme for a special case of a quadratic Euclidean 2-clustering problem”, Comput. Math. Math. Phys., 56:2 (2016), 334–341  mathnet  crossref  crossref  isi  elib
    12. 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
    13. V. V. Shenmaier, “Solving some vector subset problems by Voronoi diagrams”, J. Appl. Industr. Math., 10:4 (2016), 560–566  mathnet  crossref  crossref  mathscinet  elib
    14. 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
    15. 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:452
    Full text:109
    First page:10

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