Standard

Approximation Scheme for the Problem of Weighted 2-Clustering with a Fixed Center of One Cluster. / Kel’manov, A. V.; Motkova, A. V.; Shenmaier, V. V.

In: Proceedings of the Steklov Institute of Mathematics, Vol. 303, 01.12.2018, p. 136-145.

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

Harvard

Kel’manov, AV, Motkova, AV & Shenmaier, VV 2018, 'Approximation Scheme for the Problem of Weighted 2-Clustering with a Fixed Center of One Cluster', Proceedings of the Steklov Institute of Mathematics, vol. 303, pp. 136-145. https://doi.org/10.1134/S0081543818090146

APA

Kel’manov, A. V., Motkova, A. V., & Shenmaier, V. V. (2018). Approximation Scheme for the Problem of Weighted 2-Clustering with a Fixed Center of One Cluster. Proceedings of the Steklov Institute of Mathematics, 303, 136-145. https://doi.org/10.1134/S0081543818090146

Vancouver

Kel’manov AV, Motkova AV, Shenmaier VV. Approximation Scheme for the Problem of Weighted 2-Clustering with a Fixed Center of One Cluster. Proceedings of the Steklov Institute of Mathematics. 2018 Dec 1;303:136-145. doi: 10.1134/S0081543818090146

Author

Kel’manov, A. V. ; Motkova, A. V. ; Shenmaier, V. V. / Approximation Scheme for the Problem of Weighted 2-Clustering with a Fixed Center of One Cluster. In: Proceedings of the Steklov Institute of Mathematics. 2018 ; Vol. 303. pp. 136-145.

BibTeX

@article{8364edecbb3542f88bbe0bd0e4a4de2e,
title = "Approximation Scheme for the Problem of Weighted 2-Clustering with a Fixed Center of One Cluster",
abstract = "We consider the intractable problem of partitioning a finite set of points in Euclidean space into two clusters with minimum sum over the clusters of weighted sums of squared distances between the elements of the clusters and their centers. The center of one cluster is unknown and is defined as the mean value of its elements (i.e., it is the centroid of the cluster). The center of the other cluster is fixed at the origin. The weight factors for the intracluster sums are given as input. We present an approximation algorithm for this problem, which is based on the adaptive grid approach to finding the center of the optimal cluster. We show that the algorithm implements a fully polynomial-time approximation scheme (FPTAS) in the case of a fixed space dimension. If the dimension is not fixed but is bounded by a slowly growing function of the number of input points, the algorithm implements a polynomial-time approximation scheme (PTAS).",
keywords = "clustering, Euclidean space, FPTAS, NP-hardness, PTAS",
author = "Kel{\textquoteright}manov, {A. V.} and Motkova, {A. V.} and Shenmaier, {V. V.}",
note = "Publisher Copyright: {\textcopyright} 2018, Pleiades Publishing, Ltd.",
year = "2018",
month = dec,
day = "1",
doi = "10.1134/S0081543818090146",
language = "English",
volume = "303",
pages = "136--145",
journal = "Proceedings of the Steklov Institute of Mathematics",
issn = "0081-5438",
publisher = "Maik Nauka Publishing / Springer SBM",

}

RIS

TY - JOUR

T1 - Approximation Scheme for the Problem of Weighted 2-Clustering with a Fixed Center of One Cluster

AU - Kel’manov, A. V.

AU - Motkova, A. V.

AU - Shenmaier, V. V.

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

PY - 2018/12/1

Y1 - 2018/12/1

N2 - We consider the intractable problem of partitioning a finite set of points in Euclidean space into two clusters with minimum sum over the clusters of weighted sums of squared distances between the elements of the clusters and their centers. The center of one cluster is unknown and is defined as the mean value of its elements (i.e., it is the centroid of the cluster). The center of the other cluster is fixed at the origin. The weight factors for the intracluster sums are given as input. We present an approximation algorithm for this problem, which is based on the adaptive grid approach to finding the center of the optimal cluster. We show that the algorithm implements a fully polynomial-time approximation scheme (FPTAS) in the case of a fixed space dimension. If the dimension is not fixed but is bounded by a slowly growing function of the number of input points, the algorithm implements a polynomial-time approximation scheme (PTAS).

AB - We consider the intractable problem of partitioning a finite set of points in Euclidean space into two clusters with minimum sum over the clusters of weighted sums of squared distances between the elements of the clusters and their centers. The center of one cluster is unknown and is defined as the mean value of its elements (i.e., it is the centroid of the cluster). The center of the other cluster is fixed at the origin. The weight factors for the intracluster sums are given as input. We present an approximation algorithm for this problem, which is based on the adaptive grid approach to finding the center of the optimal cluster. We show that the algorithm implements a fully polynomial-time approximation scheme (FPTAS) in the case of a fixed space dimension. If the dimension is not fixed but is bounded by a slowly growing function of the number of input points, the algorithm implements a polynomial-time approximation scheme (PTAS).

KW - clustering

KW - Euclidean space

KW - FPTAS

KW - NP-hardness

KW - PTAS

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

U2 - 10.1134/S0081543818090146

DO - 10.1134/S0081543818090146

M3 - Article

AN - SCOPUS:85062498495

VL - 303

SP - 136

EP - 145

JO - Proceedings of the Steklov Institute of Mathematics

JF - Proceedings of the Steklov Institute of Mathematics

SN - 0081-5438

ER -

ID: 18816753