Standard

An Approximation Algorithm for a Problem of Partitioning a Sequence into Clusters with Constraints on Their Cardinalities. / Kel’manov, A. V.; Mikhailova, L. V.; Khamidullin, S. A. et al.

In: Proceedings of the Steklov Institute of Mathematics, Vol. 299, 01.12.2017, p. 88-96.

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

Harvard

Kel’manov, AV, Mikhailova, LV, Khamidullin, SA & Khandeev, VI 2017, 'An Approximation Algorithm for a Problem of Partitioning a Sequence into Clusters with Constraints on Their Cardinalities', Proceedings of the Steklov Institute of Mathematics, vol. 299, pp. 88-96. https://doi.org/10.1134/S0081543817090115

APA

Kel’manov, A. V., Mikhailova, L. V., Khamidullin, S. A., & Khandeev, V. I. (2017). An Approximation Algorithm for a Problem of Partitioning a Sequence into Clusters with Constraints on Their Cardinalities. Proceedings of the Steklov Institute of Mathematics, 299, 88-96. https://doi.org/10.1134/S0081543817090115

Vancouver

Kel’manov AV, Mikhailova LV, Khamidullin SA, Khandeev VI. An Approximation Algorithm for a Problem of Partitioning a Sequence into Clusters with Constraints on Their Cardinalities. Proceedings of the Steklov Institute of Mathematics. 2017 Dec 1;299:88-96. doi: 10.1134/S0081543817090115

Author

Kel’manov, A. V. ; Mikhailova, L. V. ; Khamidullin, S. A. et al. / An Approximation Algorithm for a Problem of Partitioning a Sequence into Clusters with Constraints on Their Cardinalities. In: Proceedings of the Steklov Institute of Mathematics. 2017 ; Vol. 299. pp. 88-96.

BibTeX

@article{b203faee4adc418e83f3a8b64129e6f3,
title = "An Approximation Algorithm for a Problem of Partitioning a Sequence into Clusters with Constraints on Their Cardinalities",
abstract = "We consider the problem of partitioning a finite sequence of points in Euclidean space into a given number of clusters (subsequences) minimizing the sum over all clusters of intracluster sums of squared distances of elements of the clusters to their centers. It is assumed that the center of one of the desired clusters is the origin, while the centers of the other clusters are unknown and are defined as the mean values of cluster elements. Additionally, there are a few structural constraints on the elements of the sequence that enter the clusters with unknown centers: (1) the concatenation of indices of elements of these clusters is an increasing sequence, (2) the difference between two consequent indices is lower and upper bounded by prescribed constants, and (3) the total number of elements in these clusters is given as an input. It is shown that the problem is strongly NP-hard. A 2-approximation algorithm that is polynomial for a fixed number of clusters is proposed for this problem.",
keywords = "approximation algorithm, Euclidean space, minimum sum of squared distances, NP-hardness, partitioning, sequence",
author = "Kel{\textquoteright}manov, {A. V.} and Mikhailova, {L. V.} and Khamidullin, {S. A.} and Khandeev, {V. I.}",
year = "2017",
month = dec,
day = "1",
doi = "10.1134/S0081543817090115",
language = "English",
volume = "299",
pages = "88--96",
journal = "Proceedings of the Steklov Institute of Mathematics",
issn = "0081-5438",
publisher = "Maik Nauka Publishing / Springer SBM",

}

RIS

TY - JOUR

T1 - An Approximation Algorithm for a Problem of Partitioning a Sequence into Clusters with Constraints on Their Cardinalities

AU - Kel’manov, A. V.

AU - Mikhailova, L. V.

AU - Khamidullin, S. A.

AU - Khandeev, V. I.

PY - 2017/12/1

Y1 - 2017/12/1

N2 - We consider the problem of partitioning a finite sequence of points in Euclidean space into a given number of clusters (subsequences) minimizing the sum over all clusters of intracluster sums of squared distances of elements of the clusters to their centers. It is assumed that the center of one of the desired clusters is the origin, while the centers of the other clusters are unknown and are defined as the mean values of cluster elements. Additionally, there are a few structural constraints on the elements of the sequence that enter the clusters with unknown centers: (1) the concatenation of indices of elements of these clusters is an increasing sequence, (2) the difference between two consequent indices is lower and upper bounded by prescribed constants, and (3) the total number of elements in these clusters is given as an input. It is shown that the problem is strongly NP-hard. A 2-approximation algorithm that is polynomial for a fixed number of clusters is proposed for this problem.

AB - We consider the problem of partitioning a finite sequence of points in Euclidean space into a given number of clusters (subsequences) minimizing the sum over all clusters of intracluster sums of squared distances of elements of the clusters to their centers. It is assumed that the center of one of the desired clusters is the origin, while the centers of the other clusters are unknown and are defined as the mean values of cluster elements. Additionally, there are a few structural constraints on the elements of the sequence that enter the clusters with unknown centers: (1) the concatenation of indices of elements of these clusters is an increasing sequence, (2) the difference between two consequent indices is lower and upper bounded by prescribed constants, and (3) the total number of elements in these clusters is given as an input. It is shown that the problem is strongly NP-hard. A 2-approximation algorithm that is polynomial for a fixed number of clusters is proposed for this problem.

KW - approximation algorithm

KW - Euclidean space

KW - minimum sum of squared distances

KW - NP-hardness

KW - partitioning

KW - sequence

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

U2 - 10.1134/S0081543817090115

DO - 10.1134/S0081543817090115

M3 - Article

AN - SCOPUS:85042147861

VL - 299

SP - 88

EP - 96

JO - Proceedings of the Steklov Institute of Mathematics

JF - Proceedings of the Steklov Institute of Mathematics

SN - 0081-5438

ER -

ID: 9961347