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

A. V. Kel’manov, A. V. Pyatkin, V. I. Khandeev

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish
Pages (from-to)163-170
Number of pages8
JournalComputational Mathematics and Mathematical Physics
Volume60
Issue number1
DOIs
Publication statusPublished - Jan 2020

Keywords

  • balanced partition
  • Euclidean space
  • NP-completeness
  • quadratic variance
  • size-weighted variance
  • variance normalized by the cluster size
  • SUM

Fingerprint Dive into the research topics of 'Complexity of Some Problems of Quadratic Partitioning of a Finite Set of Points in Euclidean Space into Balanced Clusters'. Together they form a unique fingerprint.

Cite this