Approximation Scheme for a Sequence Weighted 2-Clustering with a Fixed Center of One Cluster

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.