|
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
\Bibitem{KelPya10}
\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
\mathnet{http://mi.mathnet.ru/da623}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2779350}
\zmath{https://zbmath.org/?q=an:1249.68080}
\transl
\jour J. Appl. Industr. Math.
\yr 2011
\vol 5
\issue 3
\pages 352--357
\crossref{https://doi.org/10.1134/S1990478911030069}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-80052019433}
Linking options:
http://mi.mathnet.ru/eng/da623 http://mi.mathnet.ru/eng/da/v17/i5/p37
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:
-
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
 -
A. V. Kel'manov, “On the complexity of some cluster analysis problems”, Comput. Math. Math. Phys., 51:11 (2011), 1983–1988
 -
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
-
V. V. Shenmaier, “Approksimatsionnaya skhema dlya odnoi zadachi poiska podmnozhestva vektorov”, Diskretn. analiz i issled. oper., 19:2 (2012), 92–100
-
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
-
A. V. Kelmanov, A. V. Pyatkin, “O slozhnosti nekotorykh zadach vybora podposledovatelnosti vektorov”, Zh. vychisl. matem. i matem. fiz., 52:12 (2012), 2284–2291
-
V. V. Shenmaier, “Zadacha o minimalnom share, okhvatyvayuschem $k$ tochek”, Diskretn. analiz i issled. oper., 20:1 (2013), 93–99
-
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
 -
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
-
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
-
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
-
A. V. Kelmanov, S. M. Romanchenko, “FPTAS dlya odnoi zadachi poiska podmnozhestva vektorov”, Diskretn. analiz i issled. oper., 21:3 (2014), 41–52
-
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
-
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
-
Shenmaier V., “Complexity and Approximation of the Smallest K-Enclosing Ball Problem”, Eur. J. Comb., 48:SI (2015), 81–87
-
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
-
V. V. Shenmaier, “Reshenie nekotorykh zadach poiska podmnozhestva vektorov s ispolzovaniem diagramm Voronogo”, Diskretn. analiz i issled. oper., 23:4 (2016), 102–115
-
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
-
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
-
A. V. Kelmanov, S. M. Romanchenko, S. A. Khamidullin, “Approksimatsionnaya skhema dlya zadachi poiska podposledovatelnosti”, Sib. zhurn. vychisl. matem., 20:4 (2017), 379–392
|
| Number of views: |
| This page: | 369 | | Full text: | 108 | | References: | 38 | | First page: | 3 |
|
Terms of Use