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

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

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.

DOI: https://doi.org/10.7868/S0044466915060071

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

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
\Bibitem{KelKha15} \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 \mathnet{http://mi.mathnet.ru/zvmmf10227} \crossref{https://doi.org/10.7868/S0044466915060071} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=3358014} \elib{http://elibrary.ru/item.asp?id=23450665} \transl \jour Comput. Math. Math. Phys. \yr 2015 \vol 55 \issue 6 \pages 1068--1076 \crossref{https://doi.org/10.1134/S0965542515060068} \isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000356505400013} \elib{http://elibrary.ru/item.asp?id=23985127} \scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84934969624} 

• http://mi.mathnet.ru/eng/zvmmf10227
• http://mi.mathnet.ru/eng/zvmmf/v55/i6/p1076

 SHARE:

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
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
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
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
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
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
•  Number of views: This page: 153 Full text: 23 References: 32 First page: 9