Approximation algorithm for the problem of partitioning a sequence into clusters Full article
| Journal |
Computational Mathematics and Mathematical Physics
ISSN: 0965-5425 , E-ISSN: 1555-6662 |
||||
|---|---|---|---|---|---|
| Output data | Year: 2017, Volume: 57, Number: 8, Pages: 1376-1383 Pages count : 8 DOI: 10.1134/s0965542517080085 | ||||
| Tags | approximation algorithm; Euclidean space; minimum of the sum of squared distances; NP-hardness; partition; sequence | ||||
| Authors |
|
||||
| Affiliations |
|
Abstract:
We consider the problem of partitioning a finite sequence of Euclidean points into a given number of clusters (subsequences) using the criterion of the minimal sum (over all clusters) of intercluster sums of squared distances from the elements of the clusters to their centers. It is assumed that the center of one of the desired clusters is at the origin, while the center of each of the other clusters is unknown and determined as the mean value over all elements in this cluster. Additionally, the partition obeys two structural constraints on the indices of sequence elements contained in the clusters with unknown centers: (1) the concatenation of the indices of elements in these clusters is an increasing sequence, and (2) the difference between an index and the preceding one is bounded above and below by prescribed constants. It is shown that this problem is strongly NP-hard. A 2-approximation algorithm is constructed that is polynomial-time for a fixed number of clusters.
Cite:
Kel’manov A.V.
, Mikhailova L.V.
, Khamidullin S.A.
, Khandeev V.I.
Approximation algorithm for the problem of partitioning a sequence into clusters
Computational Mathematics and Mathematical Physics. 2017. V.57. N8. P.1376-1383. DOI: 10.1134/s0965542517080085 WOS Scopus OpenAlex
Approximation algorithm for the problem of partitioning a sequence into clusters
Computational Mathematics and Mathematical Physics. 2017. V.57. N8. P.1376-1383. DOI: 10.1134/s0965542517080085 WOS Scopus OpenAlex
Original:
Кельманов А.В.
, Михайлова Л.В.
, Хамидуллин С.А.
, Хандеев В.И.
ПРИБЛИЖЕННЫЙ АЛГОРИТМ ДЛЯ ЗАДАЧИ РАЗБИЕНИЯ ПОСЛЕДОВАТЕЛЬНОСТИ НА КЛАСТЕРЫ
Журнал вычислительной математики и математической физики. 2017. Т.57. №8. С.1392-1400. DOI: 10.7868/s0044466917080087 РИНЦ OpenAlex
ПРИБЛИЖЕННЫЙ АЛГОРИТМ ДЛЯ ЗАДАЧИ РАЗБИЕНИЯ ПОСЛЕДОВАТЕЛЬНОСТИ НА КЛАСТЕРЫ
Журнал вычислительной математики и математической физики. 2017. Т.57. №8. С.1392-1400. DOI: 10.7868/s0044466917080087 РИНЦ OpenAlex
Identifiers:
| Web of science: | WOS:000408956800011 |
| Scopus: | 2-s2.0-85028688948 |
| OpenAlex: | W2751508009 |
Citing:
| DB | Citing |
|---|---|
| OpenAlex | 1 |