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, Number 5, Pages 37–45 (Mi da623)  

This article is cited in 20 scientific papers (total in 20 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:

Document Type: Article
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, “Approksimatsionnaya skhema dlya odnoi zadachi poiska podmnozhestva vektorov”, Diskretn. analiz i issled. oper., 19:2 (2012), 92–100  mathnet  mathscinet
    5. A. V. Kelmanov, S. M. Romanchenko, S. A. Khamidullin, “Priblizhënnye algoritmy dlya nekotorykh trudnoreshaemykh zadach poiska podposledovatelnosti vektorov”, Diskretn. analiz i issled. oper., 19:3 (2012), 27–38  mathnet  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, “Zadacha o minimalnom share, okhvatyvayuschem $k$ tochek”, Diskretn. analiz i issled. oper., 20:1 (2013), 93–99  mathnet  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
    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. Kelmanov, S. M. Romanchenko, “FPTAS dlya odnoi zadachi poiska podmnozhestva vektorov”, Diskretn. analiz i issled. oper., 21:3 (2014), 41–52  mathnet  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. Kelmanov, A. V. Pyatkin, “Clozhnost zadachi o razreze maksimalnogo vesa v evklidovom prostranstve”, Diskretn. analiz i issled. oper., 21:4 (2014), 3–11  mathnet  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
    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, “Reshenie nekotorykh zadach poiska podmnozhestva vektorov s ispolzovaniem diagramm Voronogo”, Diskretn. analiz i issled. oper., 23:4 (2016), 102–115  mathnet  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. Kelmanov, A. V. Motkova, V. V. Shenmaier, “Priblizhennaya skhema dlya zadachi vzveshennoi 2-klasterizatsii s fiksirovannym tsentrom odnogo klastera”, Tr. IMM UrO RAN, 23, no. 3, 2017, 159–170  mathnet  crossref  elib
    20. A. V. Kelmanov, S. M. Romanchenko, S. A. Khamidullin, “Approksimatsionnaya skhema dlya zadachi poiska podposledovatelnosti”, Sib. zhurn. vychisl. matem., 20:4 (2017), 379–392  mathnet  crossref  elib
  • Дискретный анализ и исследование операций
    Number of views:
    This page:378
    Full text:109
    First page:3

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