|
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
\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{https://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, “Approximation scheme for one problem of a vector subset choice”, J. Appl. Industr. Math., 6:3 (2012), 381–386
-
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
-
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, “The smallest $k$-enclosing ball problem”, J. Appl. Industr. Math., 7:3 (2013), 444–448
-
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. 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
-
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. Kel'manov, A. V. Pyatkin, “Complexity of the Euclidean max cut problem”, J. Appl. Industr. Math., 8:4 (2014), 453–457
-
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, “Solving some vector subset problems by Voronoi diagrams”, J. Appl. Industr. Math., 10:4 (2016), 560–566
-
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. 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
-
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
-
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
-
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
-
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
-
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
|
| Number of views: |
| This page: | 531 | | Full text: | 165 | | References: | 54 | | First page: | 3 |
|
Terms of Use