电邮这篇文章 On the Complexity of Some Problems of Searching for a Family of Disjoint Clusters
- 作者: Kel’manov A.V.1,2, Pyatkin A.V.1,2, Khandeev V.I.1,2
-
隶属关系:
- Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences
- Novosibirsk State University
- 期: 卷 99, 编号 1 (2019)
- 页面: 52-56
- 栏目: Mathematics
- URL: https://journals.rcsi.science/1064-5624/article/view/225620
- DOI: https://doi.org/10.1134/S1064562419010162
- ID: 225620
如何引用文章
开放存取
##reader.subscriptionAccessGranted##
订阅存取
详细
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.
作者简介
A. Kel’manov
Sobolev Institute of Mathematics, Siberian Branch,Russian Academy of Sciences; Novosibirsk State University
编辑信件的主要联系方式.
Email: kelm@math.nsc.ru
俄罗斯联邦, Novosibirsk, 630090; Novosibirsk, 630090
A. Pyatkin
Sobolev Institute of Mathematics, Siberian Branch,Russian Academy of Sciences; Novosibirsk State University
编辑信件的主要联系方式.
Email: artem@math.nsc.ru
俄罗斯联邦, Novosibirsk, 630090; Novosibirsk, 630090
V. Khandeev
Sobolev Institute of Mathematics, Siberian Branch,Russian Academy of Sciences; Novosibirsk State University
编辑信件的主要联系方式.
Email: khandeev@math.nsc.ru
俄罗斯联邦, Novosibirsk, 630090; Novosibirsk, 630090
补充文件
