Мақаланы E-mail арқылы жіберу NP-Completeness of Some Problems of Partitioning a Finite Set of Points in Euclidean Space into Balanced Clusters
- Авторлар: Kel’manov A.1,2, Pyatkin A.1,2, Khandeev V.1,2
-
Мекемелер:
- Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences
- Novosibirsk State University
- Шығарылым: Том 100, № 2 (2019)
- Беттер: 416-419
- Бөлім: Mathematics
- URL: https://journals.rcsi.science/1064-5624/article/view/225709
- DOI: https://doi.org/10.1134/S1064562419050028
- ID: 225709
Дәйексөз келтіру
Ашық рұқсат
Рұқсат берілді
Тек жазылушылар үшін
Аннотация
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.
Авторлар туралы
A. Kel’manov
Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences; Novosibirsk State University
Хат алмасуға жауапты Автор.
Email: kelm@math.nsc.ru
Ресей, Novosibirsk, 630090; Novosibirsk, 630090
A. Pyatkin
Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences; Novosibirsk State University
Хат алмасуға жауапты Автор.
Email: artem@math.nsc.ru
Ресей, Novosibirsk, 630090; Novosibirsk, 630090
V. Khandeev
Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences; Novosibirsk State University
Хат алмасуға жауапты Автор.
Email: khandeev@math.nsc.ru
Ресей, Novosibirsk, 630090; Novosibirsk, 630090
