Standard

Approximation Scheme for a Quadratic Euclidean Weighted 2-Clustering Problem. / Kel’manov, A. V.; Motkova, A. V.

In: Pattern Recognition and Image Analysis, Vol. 28, No. 1, 01.01.2018, p. 17-23.

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

Harvard

Kel’manov, AV & Motkova, AV 2018, 'Approximation Scheme for a Quadratic Euclidean Weighted 2-Clustering Problem', Pattern Recognition and Image Analysis, vol. 28, no. 1, pp. 17-23. https://doi.org/10.1134/S105466181801008X

APA

Kel’manov, A. V., & Motkova, A. V. (2018). Approximation Scheme for a Quadratic Euclidean Weighted 2-Clustering Problem. Pattern Recognition and Image Analysis, 28(1), 17-23. https://doi.org/10.1134/S105466181801008X

Vancouver

Kel’manov AV, Motkova AV. Approximation Scheme for a Quadratic Euclidean Weighted 2-Clustering Problem. Pattern Recognition and Image Analysis. 2018 Jan 1;28(1):17-23. doi: 10.1134/S105466181801008X

Author

Kel’manov, A. V. ; Motkova, A. V. / Approximation Scheme for a Quadratic Euclidean Weighted 2-Clustering Problem. In: Pattern Recognition and Image Analysis. 2018 ; Vol. 28, No. 1. pp. 17-23.

BibTeX

@article{a5e4a0a445d24ee29eab5079d27ee9c8,
title = "Approximation Scheme for a Quadratic Euclidean Weighted 2-Clustering Problem",
abstract = "We consider the strongly NP-hard problem of partitioning a finite set of Euclidean points into two clusters so as to minimize the sum (over both clusters) of the weighted sums of the squared intra-cluster distances from the elements of the cluster to its center. The weights of the sums are equal to the cardinalities of the clusters. The center of one of the clusters is given as input, while the center of the other cluster is unknown and is determined as the mean value over all points in this cluster, i.e., as the geometric center (centroid). The version of the problem with constrained cardinalities of the clusters is analyzed. We construct an approximation algorithm for the problem and show that it is a fully polynomial-time approximation scheme (FPTAS) if the space dimension is bounded by a constant.",
keywords = "data analysis, Euclidean space, fixed space dimension, FPTAS, NP-hardness, weighted 2-clustering",
author = "Kel{\textquoteright}manov, {A. V.} and Motkova, {A. V.}",
year = "2018",
month = jan,
day = "1",
doi = "10.1134/S105466181801008X",
language = "English",
volume = "28",
pages = "17--23",
journal = "Pattern Recognition and Image Analysis",
issn = "1054-6618",
publisher = "Maik Nauka Publishing / Springer SBM",
number = "1",

}

RIS

TY - JOUR

T1 - Approximation Scheme for a Quadratic Euclidean Weighted 2-Clustering Problem

AU - Kel’manov, A. V.

AU - Motkova, A. V.

PY - 2018/1/1

Y1 - 2018/1/1

N2 - We consider the strongly NP-hard problem of partitioning a finite set of Euclidean points into two clusters so as to minimize the sum (over both clusters) of the weighted sums of the squared intra-cluster distances from the elements of the cluster to its center. The weights of the sums are equal to the cardinalities of the clusters. The center of one of the clusters is given as input, while the center of the other cluster is unknown and is determined as the mean value over all points in this cluster, i.e., as the geometric center (centroid). The version of the problem with constrained cardinalities of the clusters is analyzed. We construct an approximation algorithm for the problem and show that it is a fully polynomial-time approximation scheme (FPTAS) if the space dimension is bounded by a constant.

AB - We consider the strongly NP-hard problem of partitioning a finite set of Euclidean points into two clusters so as to minimize the sum (over both clusters) of the weighted sums of the squared intra-cluster distances from the elements of the cluster to its center. The weights of the sums are equal to the cardinalities of the clusters. The center of one of the clusters is given as input, while the center of the other cluster is unknown and is determined as the mean value over all points in this cluster, i.e., as the geometric center (centroid). The version of the problem with constrained cardinalities of the clusters is analyzed. We construct an approximation algorithm for the problem and show that it is a fully polynomial-time approximation scheme (FPTAS) if the space dimension is bounded by a constant.

KW - data analysis

KW - Euclidean space

KW - fixed space dimension

KW - FPTAS

KW - NP-hardness

KW - weighted 2-clustering

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

U2 - 10.1134/S105466181801008X

DO - 10.1134/S105466181801008X

M3 - Article

AN - SCOPUS:85044132177

VL - 28

SP - 17

EP - 23

JO - Pattern Recognition and Image Analysis

JF - Pattern Recognition and Image Analysis

SN - 1054-6618

IS - 1

ER -

ID: 12156045