Abstract: We consider a problem of 2-clustering of a finite sequence of points in Euclidean space. In this problem, we need to partition an input sequence into two subsequences (clusters) minimizing weighted intracluster sums of the squared distances from clusters elements to their centers. The center of the first cluster is its centroid, while the center of the second one is the origin. Some constants are used to define the boundaries of the difference between any two subsequent indices of the elements in the cluster with an unknown centroid. The problem is a generalization of previously considered problems with specific weights, as it includes the input for the weight factors for both intracluster sums. In the paper, we present an approximation algorithm. It is based on an adaptive-grid-approach and dynamic programming. If the dimension of the space is fixed, this algorithm constitutes an FPTAS.

Cite: Panasenko A.
Approximation Scheme for a Sequence Weighted 2-Clustering with a Fixed Center of One Cluster
In compilation MOTOR 2024: сборник тезисов XXIII Международной конференции «Теория математической оптимизации и исследование операций», (Омск, 30 июня – 06 июля 2024 г.). – Издательство ОмГУ., 2024. – C.75. – ISBN 978-5-7779-2691-3.

Identifiers: No identifiers

Citing: Пока нет цитирований