A fully polynomial-time approximation scheme for a sequence 2-cluster partitioning problem
- 作者: Kel’manov A.1,2, Khamidullin S.1, Khandeev V.1
-
隶属关系:
- Sobolev Institute of Mathematics
- Novosibirsk State University
- 期: 卷 10, 编号 2 (2016)
- 页面: 209-219
- 栏目: Article
- URL: https://journals.rcsi.science/1990-4789/article/view/212331
- DOI: https://doi.org/10.1134/S199047891602006X
- ID: 212331
如何引用文章
详细
We consider a strongly NP-hard problem of partitioning a finite sequence of points in Euclidean space into the two clustersminimizing the sum over both clusters of intra-cluster sums of squared distances from the clusters elements to their centers. The sizes of the clusters are fixed. The centroid of the first cluster is defined as the mean value of all vectors in the cluster, and the center of the second cluster is given in advance and equals 0. Additionally, the partition must satisfy the restriction that for all vectors in the first cluster the difference between the indices of two consequent points from this cluster is bounded from below and above by some given constants.We present a fully polynomial-time approximation scheme for the case of fixed space dimension.
作者简介
A. Kel’manov
Sobolev Institute of Mathematics; Novosibirsk State University
编辑信件的主要联系方式.
Email: kelm@math.nsc.ru
俄罗斯联邦, pr. Akad. Koptyuga 4, Novosibirsk, 630090; ul. Pirogova 2, Novosibirsk, 630090
S. Khamidullin
Sobolev Institute of Mathematics
Email: kelm@math.nsc.ru
俄罗斯联邦, pr. Akad. Koptyuga 4, Novosibirsk, 630090
V. Khandeev
Sobolev Institute of Mathematics
Email: kelm@math.nsc.ru
俄罗斯联邦, pr. Akad. Koptyuga 4, Novosibirsk, 630090