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., 2010, Volume 17, Issue 5, Pages 37–45 (Mi da623)  

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

NP-completeness of some problems of a vectors subset choice

A. V. Kel'manovab, A. V. Pyatkinab

a S. L. Sobolev Institute of Mathematics, SB RAS, Novosibirsk, Russia
b Novosibirsk State University, Novosibirsk, Russia

Abstract: One of the problem in data analysis reduces to problems of a vectors subset selection. The NP-completeness of these problems is proved. These problems are connected with searching a vector subset in a given set in Euclidian space under following conditions. The first condition is that the required subset has a given cardinality, and the second one is that this subset includes vectors which are close to each other under the criterion of minimum sum of squared distances. Bibliogr. 13.

Keywords: choice of a vector subset, clustering, algorithmic complexity, NP-completeness.

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

English version:
Journal of Applied and Industrial Mathematics, 2011, 5:3, 352–357

Bibliographic databases:

UDC: 519.2+621.391
Received: 12.04.2010
Revised: 06.07.2010

Citation: A. V. Kel'manov, A. V. Pyatkin, “NP-completeness of some problems of a vectors subset choice”, Diskretn. Anal. Issled. Oper., 17:5 (2010), 37–45; J. Appl. Industr. Math., 5:3 (2011), 352–357

Citation in format AMSBIB
\by A.~V.~Kel'manov, A.~V.~Pyatkin
\paper NP-completeness of~some problems of a~vectors subset choice
\jour Diskretn. Anal. Issled. Oper.
\yr 2010
\vol 17
\issue 5
\pages 37--45
\jour J. Appl. Industr. Math.
\yr 2011
\vol 5
\issue 3
\pages 352--357

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. A. V. Kel'manov, S. M. Romanchenko, “The approximation algorithm for one problem of searching for subset of vectors”, J. Appl. Industr. Math., 6:1 (2012), 90–96  mathnet  crossref  mathscinet  zmath
    2. 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
    3. A. V. Kel'manov, S. M. Romanchenko, “Pseudopolynomial algorithms for certain computationally hard vector subset and cluster analysis problems”, Autom. Remote Control, 73:2 (2012), 349–354  mathnet  crossref  isi
    4. V. V. Shenmaier, “Approximation scheme for one problem of a vector subset choice”, J. Appl. Industr. Math., 6:3 (2012), 381–386  mathnet  crossref  mathscinet
    5. A. V. Kel'manov, S. M. Romanchenko, S. A. Khamidullin, “Approximation algorithms for some NP-hard problems of searching a vectors subsequence”, J. Appl. Industr. Math., 6:4 (2012), 443–450  mathnet  crossref  mathscinet
    6. A. V. Kelmanov, A. V. Pyatkin, “O slozhnosti nekotorykh zadach vybora podposledovatelnosti vektorov”, Zh. vychisl. matem. i matem. fiz., 52:12 (2012), 2284–2291  mathnet
    7. V. V. Shenmaier, “The smallest $k$-enclosing ball problem”, J. Appl. Industr. Math., 7:3 (2013), 444–448  mathnet  crossref  mathscinet
    8. A. V. Kelmanov, S. M. Romanchenko, S. A. Khamidullin, “Tochnye psevdopolinomialnye algoritmy dlya nekotorykh trudnoreshaemykh zadach poiska podposledovatelnosti vektorov”, Zh. vychisl. matem. i matem. fiz., 53:1 (2013), 143–153  mathnet  crossref  elib
    9. I. I. Eremin, E. Kh. Gimadi, A. V. Kel'manov, A. V. Pyatkin, M. Yu. Khachai, “$2$-approximate algorithm for finding a clique with minimum weight of vertices and edges”, Proc. Steklov Inst. Math. (Suppl.), 284, suppl. 1 (2014), 87–95  mathnet  crossref  mathscinet  isi  elib
    10. Shenmaier V.V., “Computational Complexity and Approximation for a Generalization of the Euclidean Problem on the Chebyshev Center”, Dokl. Math., 87:3 (2013), 342–344  crossref  zmath  isi  elib  scopus
    11. A. E. Galashov, A. V. Kel'manov, “A $2$-approximate algorithm to solve one problem of the family of disjoint vector subsets”, Autom. Remote Control, 75:4 (2014), 595–606  mathnet  crossref  isi
    12. A. V. Kel'manov, S. M. Romanchenko, “FPTAS for solving a problem of search for a vector subset”, J. Appl. Industr. Math., 8:3 (2014), 329–336  mathnet  crossref  mathscinet
    13. E. Kh. Gimadi, A. V. Kel'manov, A. V. Pyatkin, M. Yu. Khachai, “Efficient algorithms with performance estimates for some problems of finding several cliques in a complete undirected weighted graph”, Proc. Steklov Inst. Math. (Suppl.), 289, suppl. 1 (2015), 88–101  mathnet  crossref  mathscinet  isi  elib
    14. A. A. Ageev, A. V. Kel'manov, A. V. Pyatkin, “Complexity of the Euclidean max cut problem”, J. Appl. Industr. Math., 8:4 (2014), 453–457  mathnet  crossref  mathscinet
    15. Shenmaier V., “Complexity and Approximation of the Smallest K-Enclosing Ball Problem”, Eur. J. Comb., 48:SI (2015), 81–87  crossref  mathscinet  zmath  isi  scopus
    16. 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
    17. 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
    18. A. E. Galashov, A. V. Kel'manov, “On pseudopolynomial-time solvability of a quadratic Euclidean problem of finding a family of disjoint subsets”, Num. Anal. Appl., 10:1 (2017), 11–16  mathnet  crossref  crossref  mathscinet  isi  elib
    19. 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
    20. A. V. Kelmanov, S. M. Romanchenko, S. A. Khamidullin, “An approximation scheme for a problem of finding a subsequence”, Num. Anal. Appl., 10:4 (2017), 313–323  mathnet  crossref  crossref  isi  elib
    21. Ageev A., Kel'manov A., Pyatkin A., Khamidullin S., Shenmaier V., “1/2-Approximation Polynomial-Time Algorithm For a Problem of Searching a Subset”, 2017 International Multi-Conference on Engineering, Computer and Information Sciences (SIBIRCON), IEEE, 2017, 8–12  crossref  isi
    22. Kel'manov A., “Efficient Approximation Algorithms For Some NP-Hard Problems of Partitioning a Set and a Sequence”, 2017 International Multi-Conference on Engineering, Computer and Information Sciences (SIBIRCON), IEEE, 2017, 87–90  crossref  isi
    23. Kel'manov A. Motkova A. Shenmaier V., “An Approximation Scheme For a Weighted Two-Cluster Partition Problem”, Analysis of Images, Social Networks and Texts, Aist 2017, Lecture Notes in Computer Science, 10716, ed. VanDerAalst W. Ignatov D. Khachay M. Kuznetsov S. Lempitsky V. Lomazova I. Loukachevitch N. Napoli A. Panchenko A. Pardalos P. Savchenko A. Wasserman S., Springer International Publishing Ag, 2018, 323–333  crossref  isi  scopus
    24. Eremeev A.V., Kel'manov A.V., Kovalyov M.Y., Pyatkin A.V., “Maximum Diversity Problem With Squared Euclidean Distance”, Mathematical Optimization Theory and Operations Research, Lecture Notes in Computer Science, 11548, eds. Khachay M., Kochetov Y., Pardalos P., Springer International Publishing Ag, 2019, 541–551  crossref  zmath  isi  scopus
  • Дискретный анализ и исследование операций
    Number of views:
    This page:531
    Full text:165
    First page:3

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