NP-Completeness of Some Problems of Partitioning a Finite Set of Points in Euclidean Space into Balanced Clusters


Citar

Texto integral

Acesso aberto Acesso aberto
Acesso é fechado Acesso está concedido
Acesso é fechado Somente assinantes

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

Arquivos suplementares
Ação
1. JATS XML

Declaração de direitos autorais © Pleiades Publishing, Ltd., 2019