NP-Completeness of Some Problems of Partitioning a Finite Set of Points in Euclidean Space into Balanced Clusters
- Autores: Kel’manov A.V.1,2, Pyatkin A.V.1,2, Khandeev V.I.1,2
-
Afiliações:
- Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences
- Novosibirsk State University
- Edição: Volume 100, Nº 2 (2019)
- Páginas: 416-419
- Seção: Mathematics
- URL: https://journals.rcsi.science/1064-5624/article/view/225709
- DOI: https://doi.org/10.1134/S1064562419050028
- ID: 225709
Citar
Resumo
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.
Sobre autores
A. Kel’manov
Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences; Novosibirsk State University
Autor responsável pela correspondência
Email: kelm@math.nsc.ru
Rússia, Novosibirsk, 630090; Novosibirsk, 630090
A. Pyatkin
Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences; Novosibirsk State University
Autor responsável pela correspondência
Email: artem@math.nsc.ru
Rússia, Novosibirsk, 630090; Novosibirsk, 630090
V. Khandeev
Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences; Novosibirsk State University
Autor responsável pela correspondência
Email: khandeev@math.nsc.ru
Rússia, Novosibirsk, 630090; Novosibirsk, 630090
Arquivos suplementares
