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

A. V. Kel’manov; A. V. Pyatkin; V. I. Khandeev

doi:10.1134/S1064562419050028

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

A. V. Kel’manov, A. V. Pyatkin, V. I. Khandeev

Результат исследования: Научные публикации в периодических изданиях › статья › рецензирование

Аннотация

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.

Язык оригинала	английский
Страницы (с-по)	416-419
Число страниц	4
Журнал	Doklady Mathematics
Том	100
Номер выпуска	2
DOI	https://doi.org/10.1134/S1064562419050028
Состояние	Опубликовано - 1 сен 2019

Доступ к документу

10.1134/S1064562419050028

Link to publication in Scopus

Fingerprint Подробные сведения о темах исследования «NP-Completeness of Some Problems of Partitioning a Finite Set of Points in Euclidean Space into Balanced Clusters». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать

@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.}",

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",

}

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.

В: Doklady Mathematics, Том 100, № 2, 01.09.2019, стр. 416-419.

Результат исследования: Научные публикации в периодических изданиях › статья › рецензирование

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.

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 -