Open AccessOn the complexity of some problems of searching for a family of disjoint clusters
Author(s) -
А. В. Кельманов,
A. V. Pyatkin,
В. И. Хандеев
Publication year - 2019
Publication title -
doklady akademii nauk. rossijskaâ akademiâ nauk
Language(s) - English
Resource type - Journals
ISSN - 0869-5652
DOI - 10.31857/s0869-56524844387-392
Subject(s) - disjoint sets , combinatorics , mathematics , centroid , quadratic equation , euclidean space , constant (computer programming) , set (abstract data type) , variation (astronomy) , euclidean distance , computer science , geometry , physics , astrophysics , programming language
We consider some consimilar problems of searching for disjoint subsets (clusters) in the nite set of points in Euclidean space. In these problems, it is required to maximize the minimum subset size such that the value of each intracluster quadratic variation would not exceed a given fraction (constant) of the total quadratic variation of the points of the input set with respect to its centroid. In the paper, we have proved that all the problems are NP-hard even on a line.