RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Zh. Vychisl. Mat. Mat. Fiz.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Zh. Vychisl. Mat. Mat. Fiz., 2010, Volume 50, Number 11, Pages 2045–2051 (Mi zvmmf4971)  

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

On the complexity of some data analysis problems

A. V. Kel'manov

Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences, pr. Akademika Koptyuga 4, Novosibirsk, 630090 Russia

Abstract: NP-completeness of certain discrete optimization problems is proved. These are the problems to which one can reduce some important problems arising in data analysis when certain subsets of vectors are sought.

Key words: discrete optimization problem, complexity, NP-completeness, finding subsets of vectors in the Euclidean space, data analysis.

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

English version:
Computational Mathematics and Mathematical Physics, 2010, 50:11, 1941–1947

Bibliographic databases:

UDC: 519.7
Received: 14.01.2010
Revised: 16.06.2010

Citation: A. V. Kel'manov, “On the complexity of some data analysis problems”, Zh. Vychisl. Mat. Mat. Fiz., 50:11 (2010), 2045–2051; Comput. Math. Math. Phys., 50:11 (2010), 1941–1947

Citation in format AMSBIB
\Bibitem{Kel10}
\by A.~V.~Kel'manov
\paper On the complexity of some data analysis problems
\jour Zh. Vychisl. Mat. Mat. Fiz.
\yr 2010
\vol 50
\issue 11
\pages 2045--2051
\mathnet{http://mi.mathnet.ru/zvmmf4971}
\adsnasa{http://adsabs.harvard.edu/cgi-bin/bib_query?2010CMMPh..50.1941K}
\transl
\jour Comput. Math. Math. Phys.
\yr 2010
\vol 50
\issue 11
\pages 1941--1947
\crossref{https://doi.org/10.1134/S0965542510110163}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000284649800016}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-78649766487}


Linking options:
  • http://mi.mathnet.ru/eng/zvmmf4971
  • http://mi.mathnet.ru/eng/zvmmf/v50/i11/p2045

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    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, “On the complexity of some cluster analysis problems”, Comput. Math. Math. Phys., 51:11 (2011), 1983–1988  mathnet  crossref  mathscinet  isi
    2. A. V. Kel'manov, V. I. Khandeev, “An exact pseudopolynomial algorithm for a bi-partitioning problem”, J. Appl. Industr. Math., 9:4 (2015), 497–502  mathnet  crossref  crossref  mathscinet  elib
    3. 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
    4. A. V. Kel'manov, V. I. Khandeev, “A randomized algorithm for two-cluster partition of a set of vectors”, Comput. Math. Math. Phys., 55:2 (2015), 330–339  mathnet  crossref  crossref  mathscinet  isi  elib  elib
    5. Kel'manov A.V., Pyatkin A.V., “NP-Hardness of Some Quadratic Euclidean 2-Clustering Problems”, Dokl. Math., 92:2 (2015), 634–637  crossref  mathscinet  zmath  isi  scopus
    6. 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
    7. A. V. Kel'manov, A. V. Pyatkin, “On the complexity of some quadratic Euclidean 2-clustering problems”, Comput. Math. Math. Phys., 56:3 (2016), 491–497  mathnet  crossref  elib
    8. A. V. Kel'manov, S. A. Khamidullin, V. I. Khandeev, “Fully polynomial-time approximation scheme for a sequence $2$-clustering problem”, J. Appl. Industr. Math., 10:2 (2016), 209–219  mathnet  crossref  crossref  mathscinet  elib
    9. 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  mathscinet  isi  scopus
  • Журнал вычислительной математики и математической физики Computational Mathematics and Mathematical Physics
    Number of views:
    This page:224
    Full text:73
    References:43
    First page:11

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