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

Standard

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.

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

BibTeX

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

}

RIS

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 -

ID: 23950041