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., 2013, Volume 20, Number 2, Pages 47–57 (Mi da725)  

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

On the complexity of some vector sequence clustering problems

A. V. Kel'manov, A. V. Pyatkin

Sobolev Institute of Mathematics, Novosibirsk, Russia

Abstract: It is proved that two problems of clusterization (partition) of a finite Euclidean vectors sequence are NP-complete. In the optimization versions of these problems the aim is to partition the elements of the sequence into a fixed number of clusters minimizing the sum of the squares of the distances from the clusters' elements to their centers. In one of the problems the cardinalities of the clusters are the part of input while in the other problem they are not (they are the optimization variables). Except the center of one-special-cluster, centers of all other clusters are defined as the mean values of all vectors in the cluster. The center of the special cluster is given in advance and is equal to 0. Moreover, the partition must satisfy the restriction that for all vectors that are not in the special cluster the difference between the indices of two consequent vectors from any of these clusters is bounded from below and above by some constants. Bibliogr. 20.

Keywords: clusterization, Euclidean vectors sequence, MSSC, restriction on indices, algorithmic complexity.

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

English version:
Journal of Applied and Industrial Mathematics, 2013, 7:3, 363–369

Bibliographic databases:

UDC: 519.2+621.391
Received: 27.06.2012
Revised: 11.10.2012

Citation: A. V. Kel'manov, A. V. Pyatkin, “On the complexity of some vector sequence clustering problems”, Diskretn. Anal. Issled. Oper., 20:2 (2013), 47–57; J. Appl. Industr. Math., 7:3 (2013), 363–369

Citation in format AMSBIB
\by A.~V.~Kel'manov, A.~V.~Pyatkin
\paper On the complexity of some vector sequence clustering problems
\jour Diskretn. Anal. Issled. Oper.
\yr 2013
\vol 20
\issue 2
\pages 47--57
\jour J. Appl. Industr. Math.
\yr 2013
\vol 7
\issue 3
\pages 363--369

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. Yu. Yu. Velikanova, “Algoritmy dlya odnoi zadachi o nakhozhdenii maksimuma unimodalnoi funktsii v rezhime online”, Diskretn. analiz i issled. oper., 20:6 (2013), 16–29  mathnet  mathscinet
    2. A. V. Kelmanov, S. A. Khamidullin, “Approximation algorithm for one problem of partitioning a sequence”, J. Appl. Industr. Math., 8:2 (2014), 236–244  mathnet  crossref  mathscinet
    3. 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
    4. A. V. Orlov, “Chislennyi poisk globalnykh reshenii v zadachakh nesimmetrichnoi bilineinoi otdelimosti”, Diskretn. analiz i issled. oper., 22:1 (2015), 64–85  mathnet  crossref  mathscinet  elib
    5. 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
    6. A. V. Kel'manov, S. A. Khamidullin, “An approximation polynomial-time algorithm for a sequence bi-clustering problem”, Comput. Math. Math. Phys., 55:6 (2015), 1068–1076  mathnet  crossref  crossref  mathscinet  isi  elib  elib
    7. 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
    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. A. V. Kel'manov, L. V. Mikhailova, S. A. Khamidullin, V. I. Khandeev, “An approximation algorithm for the problem of partitioning a sequence into clusters with constraints on their cardinalities”, Proc. Steklov Inst. Math. (Suppl.), 299, suppl. 1 (2017), 88–96  mathnet  crossref  crossref  mathscinet  isi  elib
    10. A. V. Eremeev, A. V. Kel'manov, A. V. Pyatkin, “On the complexity and approximability of some Euclidean optimal summing problems”, Comput. Math. Math. Phys., 56:10 (2016), 1813–1817  mathnet  crossref  crossref  isi  elib
    11. A. V. Kel'manov, S. A. Khamidullin, V. I. Khandeev, “Exact pseudopolynomial algorithm for one sequence partitioning problem”, Autom. Remote Control, 78:1 (2017), 67–74  mathnet  crossref  isi  elib
    12. A. V. Kel'manov, L. V. Mikhailova, S. A. Khamidullin, V. I. Khandeev, “Approximation algorithm for the problem of partitioning a sequence into clusters”, Comput. Math. Math. Phys., 57:8 (2017), 1376–1383  mathnet  crossref  crossref  isi  elib
    13. A. Kel'manov, “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
    14. A. V. Kel'manov, S. A. Khamidullin, V. I. Khandeev, “A randomized algorithm for a sequence 2-clustering problem”, Comput. Math. Math. Phys., 58:12 (2018), 2078–2085  mathnet  crossref  crossref  isi  elib
    15. A. Kel'manov, S. Khamidullin, V. Khandeev, “A randomized algorithm for 2-partition of a sequence”, Analysis of Images, Social Networks and Texts, AIST 2017, Lecture Notes in Computer Science, 10716, eds. W. van der Aalst, D. Ignatov, M. Khachay, S. Kuznetsov, V. Lempitsky, I. Lomazova, N. Loukachevitch, A. Napoli, A. Panchenko, P. Pardalos, A. Savchenko, S. Wasserman, Springer, 2018, 313–322  crossref  isi  scopus
  • Дискретный анализ и исследование операций
    Number of views:
    This page:303
    Full text:70
    First page:10

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