Standard

Approximation algorithm for the problem of partitioning a sequence into clusters. / Kel’manov, A. V.; Mikhailova, L. V.; Khamidullin, S. A. et al.

In: Computational Mathematics and Mathematical Physics, Vol. 57, No. 8, 01.08.2017, p. 1376-1383.

Research output: Contribution to journal › Article › peer-review

Harvard

Kel’manov, AV, Mikhailova, LV, Khamidullin, SA & Khandeev, VI 2017, 'Approximation algorithm for the problem of partitioning a sequence into clusters', Computational Mathematics and Mathematical Physics, vol. 57, no. 8, pp. 1376-1383. https://doi.org/10.1134/S0965542517080085

APA

Kel’manov, A. V., Mikhailova, L. V., Khamidullin, S. A., & Khandeev, V. I. (2017). Approximation algorithm for the problem of partitioning a sequence into clusters. Computational Mathematics and Mathematical Physics, 57(8), 1376-1383. https://doi.org/10.1134/S0965542517080085

Vancouver

Kel’manov AV, Mikhailova LV, Khamidullin SA, Khandeev VI. Approximation algorithm for the problem of partitioning a sequence into clusters. Computational Mathematics and Mathematical Physics. 2017 Aug 1;57(8):1376-1383. doi: 10.1134/S0965542517080085

Author

Kel’manov, A. V. ; Mikhailova, L. V. ; Khamidullin, S. A. et al. / Approximation algorithm for the problem of partitioning a sequence into clusters. In: Computational Mathematics and Mathematical Physics. 2017 ; Vol. 57, No. 8. pp. 1376-1383.

BibTeX

@article{2507519ad1e04307983e2578fbbbffb8,
title = "Approximation algorithm for the problem of partitioning a sequence into clusters",
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.",
keywords = "approximation algorithm, Euclidean space, minimum of the sum of squared distances, NP-hardness, partition, sequence",
author = "Kel{\textquoteright}manov, {A. V.} and Mikhailova, {L. V.} and Khamidullin, {S. A.} and Khandeev, {V. I.}",
note = "Publisher Copyright: {\textcopyright} 2017, Pleiades Publishing, Ltd.",
year = "2017",
month = aug,
day = "1",
doi = "10.1134/S0965542517080085",
language = "English",
volume = "57",
pages = "1376--1383",
journal = "Computational Mathematics and Mathematical Physics",
issn = "0965-5425",
publisher = "PLEIADES PUBLISHING INC",
number = "8",

}

RIS

TY - JOUR

T1 - Approximation algorithm for the problem of partitioning a sequence into clusters

AU - Kel’manov, A. V.

AU - Mikhailova, L. V.

AU - Khamidullin, S. A.

AU - Khandeev, V. I.

N1 - Publisher Copyright: © 2017, Pleiades Publishing, Ltd.

PY - 2017/8/1

Y1 - 2017/8/1

N2 - 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.

AB - 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.

KW - approximation algorithm

KW - Euclidean space

KW - minimum of the sum of squared distances

KW - NP-hardness

KW - partition

KW - sequence

UR - http://www.scopus.com/inward/record.url?scp=85028688948&partnerID=8YFLogxK

U2 - 10.1134/S0965542517080085

DO - 10.1134/S0965542517080085

M3 - Article

AN - SCOPUS:85028688948

VL - 57

SP - 1376

EP - 1383

JO - Computational Mathematics and Mathematical Physics

JF - Computational Mathematics and Mathematical Physics

SN - 0965-5425

IS - 8

ER -

ID: 9916600