Approximation algorithm for the problem of partitioning a sequence into clusters


如何引用文章

全文:

开放存取 开放存取
受限制的访问 ##reader.subscriptionAccessGranted##
受限制的访问 订阅存取

详细

We consider the problem of partitioning a finite sequence of Euclidean points into a given number of clusters (subsequences) using the criterion of the minimal sum (over all clusters) of intercluster sums of squared distances from the elements of the clusters to their centers. It is assumed that the center of one of the desired clusters is at the origin, while the center of each of the other clusters is unknown and determined as the mean value over all elements in this cluster. Additionally, the partition obeys two structural constraints on the indices of sequence elements contained in the clusters with unknown centers: (1) the concatenation of the indices of elements in these clusters is an increasing sequence, and (2) the difference between an index and the preceding one is bounded above and below by prescribed constants. It is shown that this problem is strongly NP-hard. A 2-approximation algorithm is constructed that is polynomial-time for a fixed number of clusters.

作者简介

A. Kel’manov

Sobolev Institute of Mathematics, Siberian Branch; Novosibirsk State University

编辑信件的主要联系方式.
Email: kelm@math.nsc.ru
俄罗斯联邦, Novosibirsk, 630090; Novosibirsk, 630090

L. Mikhailova

Sobolev Institute of Mathematics, Siberian Branch

Email: kelm@math.nsc.ru
俄罗斯联邦, Novosibirsk, 630090

S. Khamidullin

Sobolev Institute of Mathematics, Siberian Branch

Email: kelm@math.nsc.ru
俄罗斯联邦, Novosibirsk, 630090

V. Khandeev

Sobolev Institute of Mathematics, Siberian Branch; Novosibirsk State University

Email: kelm@math.nsc.ru
俄罗斯联邦, Novosibirsk, 630090; Novosibirsk, 630090

补充文件

附件文件
动作
1. JATS XML

版权所有 © Pleiades Publishing, Ltd., 2017