Standard

NP-hardness of quadratic euclidean 1-mean and 1-median 2-clustering problem with constraints on the cluster sizes. / Kel’manov, A. V.; Pyatkin, A. V.; Khandeev, V. I.

In: Doklady Mathematics, Vol. 100, No. 3, 11.2019, p. 545-548.

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

Harvard

Kel’manov, AV, Pyatkin, AV & Khandeev, VI 2019, 'NP-hardness of quadratic euclidean 1-mean and 1-median 2-clustering problem with constraints on the cluster sizes', Doklady Mathematics, vol. 100, no. 3, pp. 545-548. https://doi.org/10.1134/S1064562419060127

APA

Kel’manov, A. V., Pyatkin, A. V., & Khandeev, V. I. (2019). NP-hardness of quadratic euclidean 1-mean and 1-median 2-clustering problem with constraints on the cluster sizes. Doklady Mathematics, 100(3), 545-548. https://doi.org/10.1134/S1064562419060127

Vancouver

Kel’manov AV, Pyatkin AV, Khandeev VI. NP-hardness of quadratic euclidean 1-mean and 1-median 2-clustering problem with constraints on the cluster sizes. Doklady Mathematics. 2019 Nov;100(3):545-548. doi: 10.1134/S1064562419060127

Author

Kel’manov, A. V. ; Pyatkin, A. V. ; Khandeev, V. I. / NP-hardness of quadratic euclidean 1-mean and 1-median 2-clustering problem with constraints on the cluster sizes. In: Doklady Mathematics. 2019 ; Vol. 100, No. 3. pp. 545-548.

BibTeX

@article{85fcc8f1fdef448383756efda5c24ec2,
title = "NP-hardness of quadratic euclidean 1-mean and 1-median 2-clustering problem with constraints on the cluster sizes",
abstract = "We consider the problem of clustering a finite set of N points in d-dimensional Euclidean space into two clusters minimizing the sum (over both clusters) of the intracluster sums of the squared distances between the cluster elements and their centers. The center of one cluster is defined as a centroid (geometric center). The center of the other cluster is determined as an optimized point in the input set. We analyze the variant of the problem with given cluster sizes such that their sum is equal to the size of the input set. The strong NP-hardness of this problem is proved.",
author = "Kel{\textquoteright}manov, {A. V.} and Pyatkin, {A. V.} and Khandeev, {V. I.}",
year = "2019",
month = nov,
doi = "10.1134/S1064562419060127",
language = "English",
volume = "100",
pages = "545--548",
journal = "Doklady Mathematics",
issn = "1064-5624",
publisher = "Maik Nauka-Interperiodica Publishing",
number = "3",

}

RIS

TY - JOUR

T1 - NP-hardness of quadratic euclidean 1-mean and 1-median 2-clustering problem with constraints on the cluster sizes

AU - Kel’manov, A. V.

AU - Pyatkin, A. V.

AU - Khandeev, V. I.

PY - 2019/11

Y1 - 2019/11

N2 - We consider the problem of clustering a finite set of N points in d-dimensional Euclidean space into two clusters minimizing the sum (over both clusters) of the intracluster sums of the squared distances between the cluster elements and their centers. The center of one cluster is defined as a centroid (geometric center). The center of the other cluster is determined as an optimized point in the input set. We analyze the variant of the problem with given cluster sizes such that their sum is equal to the size of the input set. The strong NP-hardness of this problem is proved.

AB - We consider the problem of clustering a finite set of N points in d-dimensional Euclidean space into two clusters minimizing the sum (over both clusters) of the intracluster sums of the squared distances between the cluster elements and their centers. The center of one cluster is defined as a centroid (geometric center). The center of the other cluster is determined as an optimized point in the input set. We analyze the variant of the problem with given cluster sizes such that their sum is equal to the size of the input set. The strong NP-hardness of this problem is proved.

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

U2 - 10.1134/S1064562419060127

DO - 10.1134/S1064562419060127

M3 - Article

AN - SCOPUS:85081681028

VL - 100

SP - 545

EP - 548

JO - Doklady Mathematics

JF - Doklady Mathematics

SN - 1064-5624

IS - 3

ER -

ID: 23825697