General information
Latest issue
Impact factor

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Zh. Vychisl. Mat. Mat. Fiz.:

Personal entry:
Save password
Forgotten password?

Zh. Vychisl. Mat. Mat. Fiz., 2015, Volume 55, Number 6, Pages 1076–1085 (Mi zvmmf10227)  

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

An approximation polynomial-time algorithm for a sequence bi-clustering problem

A. V. Kel'manovab, S. A. Khamidullina

a Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences, pr. Akademika Koptyuga 4, Novosibirsk, 630090, Russia
b Novosibirsk State University, ul. Pirogova 2, Novosibirsk, 630090, Russia

Abstract: We consider a strongly NP-hard problem of partitioning a finite sequence of vectors in Euclidean space into two clusters using the criterion of the minimal sum of the squared distances from the elements of the clusters to the centers of the clusters. The center of one of the clusters is to be optimized and is determined as the mean value over all vectors in this cluster. The center of the other cluster is fixed at the origin. Moreover, the partition is such that the difference between the indices of two successive vectors in the first cluster is bounded above and below by prescribed constants. A 2-approximation polynomial-time algorithm is proposed for this problem.

Key words: sequence of Euclidean vectors, clustering, minimum of the sum of squared distances, NP-hardness, approximation polynomial-time algorithm.


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

English version:
Computational Mathematics and Mathematical Physics, 2015, 55:6, 1068–1076

Bibliographic databases:

UDC: 519.7
Received: 23.01.2014

Citation: A. V. Kel'manov, S. A. Khamidullin, “An approximation polynomial-time algorithm for a sequence bi-clustering problem”, Zh. Vychisl. Mat. Mat. Fiz., 55:6 (2015), 1076–1085; Comput. Math. Math. Phys., 55:6 (2015), 1068–1076

Citation in format AMSBIB
\by A.~V.~Kel'manov, S.~A.~Khamidullin
\paper An approximation polynomial-time algorithm for a sequence bi-clustering problem
\jour Zh. Vychisl. Mat. Mat. Fiz.
\yr 2015
\vol 55
\issue 6
\pages 1076--1085
\jour Comput. Math. Math. Phys.
\yr 2015
\vol 55
\issue 6
\pages 1068--1076

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. 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
    2. L. I. Rubanov, A. V. Seliverstov, O. A. Zverkov, V. A. Lyubetsky, “A method for identification of highly conserved elements and evolutionary analysis of superphylum Alveolata”, BMC Bioinformatics, 17 (2016), 385  crossref  isi  elib  scopus
    3. 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
    4. 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 2017, IEEE, 2017, 87–90  crossref  isi
    5. A. R. Aydinyan, O. L. Tsvetkova, “The cluster algorithms for solving problems with asymmetric proximity measures”, Num. Anal. Appl., 11:2 (2018), 99–107  mathnet  crossref  crossref  isi  elib  elib
    6. 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
  • Журнал вычислительной математики и математической физики Computational Mathematics and Mathematical Physics
    Number of views:
    This page:153
    Full text:23
    First page:9

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