电邮这篇文章 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
如何引用文章
开放存取
##reader.subscriptionAccessGranted##
订阅存取
详细
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
