Standard

NP-Completeness of Some Problems of Partitioning a Finite Set of Points in Euclidean Space into Balanced Clusters. / Kel’manov, A. V.; Pyatkin, A. V.; Khandeev, V. I.

In: Doklady Mathematics, Vol. 100, No. 2, 01.09.2019, p. 416-419.

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

Harvard

Kel’manov, AV, Pyatkin, AV & Khandeev, VI 2019, 'NP-Completeness of Some Problems of Partitioning a Finite Set of Points in Euclidean Space into Balanced Clusters', Doklady Mathematics, vol. 100, no. 2, pp. 416-419. https://doi.org/10.1134/S1064562419050028

APA

Kel’manov, A. V., Pyatkin, A. V., & Khandeev, V. I. (2019). NP-Completeness of Some Problems of Partitioning a Finite Set of Points in Euclidean Space into Balanced Clusters. Doklady Mathematics, 100(2), 416-419. https://doi.org/10.1134/S1064562419050028

Vancouver

Kel’manov AV, Pyatkin AV, Khandeev VI. NP-Completeness of Some Problems of Partitioning a Finite Set of Points in Euclidean Space into Balanced Clusters. Doklady Mathematics. 2019 Sept 1;100(2):416-419. doi: 10.1134/S1064562419050028

Author

Kel’manov, A. V. ; Pyatkin, A. V. ; Khandeev, V. I. / NP-Completeness of Some Problems of Partitioning a Finite Set of Points in Euclidean Space into Balanced Clusters. In: Doklady Mathematics. 2019 ; Vol. 100, No. 2. pp. 416-419.

BibTeX

@article{a01fd1bc0fea41a59e7d2632e16f0146,
title = "NP-Completeness of Some Problems of Partitioning a Finite Set of Points in Euclidean Space into Balanced Clusters",
abstract = "We consider three related problems of partitioning an N-element set of points in d-dimensional Euclidean space into two clusters balancing the value of (1) the intracluster quadratic variance normalized by the cluster size in the first problem; (2) the intracluster quadratic variance in the second problem; and (3) the size-weighted intracluster quadratic variance in the third problem. The NP-completeness of all these problems is proved.",
author = "Kel{\textquoteright}manov, {A. V.} and Pyatkin, {A. V.} and Khandeev, {V. I.}",
note = "Publisher Copyright: {\textcopyright} 2019, Pleiades Publishing, Ltd.",
year = "2019",
month = sep,
day = "1",
doi = "10.1134/S1064562419050028",
language = "English",
volume = "100",
pages = "416--419",
journal = "Doklady Mathematics",
issn = "1064-5624",
publisher = "Maik Nauka-Interperiodica Publishing",
number = "2",

}

RIS

TY - JOUR

T1 - NP-Completeness of Some Problems of Partitioning a Finite Set of Points in Euclidean Space into Balanced Clusters

AU - Kel’manov, A. V.

AU - Pyatkin, A. V.

AU - Khandeev, V. I.

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

PY - 2019/9/1

Y1 - 2019/9/1

N2 - We consider three related problems of partitioning an N-element set of points in d-dimensional Euclidean space into two clusters balancing the value of (1) the intracluster quadratic variance normalized by the cluster size in the first problem; (2) the intracluster quadratic variance in the second problem; and (3) the size-weighted intracluster quadratic variance in the third problem. The NP-completeness of all these problems is proved.

AB - We consider three related problems of partitioning an N-element set of points in d-dimensional Euclidean space into two clusters balancing the value of (1) the intracluster quadratic variance normalized by the cluster size in the first problem; (2) the intracluster quadratic variance in the second problem; and (3) the size-weighted intracluster quadratic variance in the third problem. The NP-completeness of all these problems is proved.

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

U2 - 10.1134/S1064562419050028

DO - 10.1134/S1064562419050028

M3 - Article

AN - SCOPUS:85075150257

VL - 100

SP - 416

EP - 419

JO - Doklady Mathematics

JF - Doklady Mathematics

SN - 1064-5624

IS - 2

ER -

ID: 22319261