On the Complexity of Some Problems of Searching for a Family of Disjoint Clusters

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

Research output: Contribution to journalArticlepeer-review

Abstract

Abstract: Two consimilar problems of searching for a family of disjoint subsets (clusters) in a finite set of points of Euclidean space are considered. In these problems, the task is to maximize the minimum cluster size so that the value of each intercluster quadratic variation does not exceed a given fraction (constant) of the total quadratic variation of the points of the input set with respect to its centroid. Both problems are proved to be NP-hard even on a line.

Original languageEnglish
Pages (from-to)52-56
Number of pages5
JournalDoklady Mathematics
Volume99
Issue number1
DOIs
Publication statusPublished - 1 Jan 2019

Keywords

  • ALGORITHM
  • 2-CENTER

Fingerprint

Dive into the research topics of 'On the Complexity of Some Problems of Searching for a Family of Disjoint Clusters'. Together they form a unique fingerprint.

Cite this