Complexity of Some Problems of Quadratic Partitioning of a Finite Set of Points in Euclidean Space into Balanced Clusters

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

doi:10.1134/S096554251911006X

Complexity of Some Problems of Quadratic Partitioning of 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 the intracluster quadratic variance normalized by the cluster size in the first problem, the intracluster quadratic variance in the second problem, and the size-weighted intracluster variance in the third problem. The NP-completeness of all these problems is proved.

Язык оригинала	английский
Страницы (с-по)	163-170
Число страниц	8
Журнал	Computational Mathematics and Mathematical Physics
Том	60
Номер выпуска	1
DOI	https://doi.org/10.1134/S096554251911006X
Состояние	Опубликовано - янв 2020

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

10.1134/S096554251911006X

Link to publication in Scopus

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

Цитировать

@article{0080bd29baa0495eba9b4ca306e2e4a6,

title = "Complexity of Some Problems of Quadratic Partitioning of 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 the intracluster quadratic variance normalized by the cluster size in the first problem, the intracluster quadratic variance in the second problem, and the size-weighted intracluster variance in the third problem. The NP-completeness of all these problems is proved.",

keywords = "balanced partition, Euclidean space, NP-completeness, quadratic variance, size-weighted variance, variance normalized by the cluster size, SUM",

author = "Kel{\textquoteright}manov, {A. V.} and Pyatkin, {A. V.} and Khandeev, {V. I.}",

year = "2020",

month = jan,

doi = "10.1134/S096554251911006X",

language = "English",

volume = "60",

pages = "163--170",

journal = "Computational Mathematics and Mathematical Physics",

issn = "0965-5425",

publisher = "PLEIADES PUBLISHING INC",

number = "1",

}

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

В: Computational Mathematics and Mathematical Physics, Том 60, № 1, 01.2020, стр. 163-170.

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

TY - JOUR

T1 - Complexity of Some Problems of Quadratic Partitioning of 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 - 2020/1

Y1 - 2020/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 the intracluster quadratic variance normalized by the cluster size in the first problem, the intracluster quadratic variance in the second problem, and the size-weighted intracluster 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 the intracluster quadratic variance normalized by the cluster size in the first problem, the intracluster quadratic variance in the second problem, and the size-weighted intracluster variance in the third problem. The NP-completeness of all these problems is proved.

KW - balanced partition

KW - Euclidean space

KW - NP-completeness

KW - quadratic variance

KW - size-weighted variance

KW - variance normalized by the cluster size

KW - SUM

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

U2 - 10.1134/S096554251911006X

DO - 10.1134/S096554251911006X

M3 - Article

AN - SCOPUS:85082601642

VL - 60

SP - 163

EP - 170

JO - Computational Mathematics and Mathematical Physics

JF - Computational Mathematics and Mathematical Physics

SN - 0965-5425

IS - 1

ER -