Geodesic
An approximation polynomial-time algorithm for a sequence bi-clustering problem
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 55 (2015) no. 6, pp. 1076-1085

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{ZVMMF_2015_55_6_a13,
     author = {A. V. Kel'manov and S. A. Khamidullin},
     title = {An approximation polynomial-time algorithm for a sequence bi-clustering problem},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {1076--1085},
     publisher = {mathdoc},
     volume = {55},
     number = {6},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2015_55_6_a13/}
}
TY  - JOUR
AU  - A. V. Kel'manov
AU  - S. A. Khamidullin
TI  - An approximation polynomial-time algorithm for a sequence bi-clustering problem
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2015
SP  - 1076
EP  - 1085
VL  - 55
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2015_55_6_a13/
LA  - ru
ID  - ZVMMF_2015_55_6_a13
ER  - 
%0 Journal Article
%A A. V. Kel'manov
%A S. A. Khamidullin
%T An approximation polynomial-time algorithm for a sequence bi-clustering problem
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2015
%P 1076-1085
%V 55
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ZVMMF_2015_55_6_a13/
%G ru
%F ZVMMF_2015_55_6_a13
A. V. Kel'manov; S. A. Khamidullin. An approximation polynomial-time algorithm for a sequence bi-clustering problem. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 55 (2015) no. 6, pp. 1076-1085. http://geodesic.mathdoc.fr/item/ZVMMF_2015_55_6_a13/