Approximation algorithm for the problem of partitioning a sequence into clusters

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 2-approximation polynomial algorithm for a clustering problem

A 2-approximation algorithm is presented for some NP-hard data analysis problem that consists in partitioning a set of Euclidean vectors into two subsets (clusters) under the criterion of minimum sum-of-squares of distances from the elements of clusters to their centers. The center of the first cluster is the average value of vectors in the cluster, and the center of the second one is the origin.     

Randomized Algorithms for Some Hard-to-Solve Problems of Clustering a Finite Set of Points in Euclidean Space

Computational Mathematics and Mathematical Physics - Two strongly NP-hard problems of clustering a finite set of points in Euclidean space are considered. In the first problem, given an input set,...     

A Randomized Algorithm for a Sequence 2-Clustering Problem

Computational Mathematics and Mathematical Physics - We consider a strongly NP-hard problem of partitioning a finite Euclidean sequence into two clusters of given cardinalities minimizing the sum...     

On Polynomial Solvability of One Quadratic Euclidean Clustering Problem on a Line

Doklady Mathematics - We consider the problem of partitioning a finite set of points in Euclidean space into clusters so as to minimize the sum, over all clusters, of the intracluster sums of the...     

An Approximation Algorithm for a Problem of Partitioning a Sequence into Clusters with Constraints on Their Cardinalities

We give a slight refinement to the process by which estimates for exponential sums are extracted from bounds for Vinogradov’s mean value. Coupling this with the recent works of Wooley, and of Bourgain, Demeter and Guth, providing optimal bounds for the Vinogradov mean value, we produce a powerful new kth derivative estimate. Roughly speaking, this improves the van der Corput estimate for k ≥ 4. Various corollaries are given, showing for example that \(\zeta \left( {\sigma + it} \right){ \ll _\varepsilon }{t^{{{\left( {1 - \sigma } \right)}^{3/2}}/2 + \varepsilon }}\) for t ≥ 2 and 0 ≤ σ ≤ 1, for any fixed ε > 0.     

NP-Completeness of Some Problems of Partitioning a Finite Set of Points in Euclidean Space into Balanced Clusters

Doklady Mathematics - We consider three related problems of partitioning an $$N$$-element set of points in $$d$$-dimensional Euclidean space into two clusters balancing the value of (1) the...     

A fully polynomial-time approximation scheme for a sequence 2-cluster partitioning problem

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.     

NP-Hardness of Quadratic Euclidean 1-Mean and 1-Median 2-Clustering Problem with Constraints on the Cluster Sizes

Doklady Mathematics - We consider the problem of clustering a finite set of N points in d-dimensional Euclidean space into two clusters minimizing the sum (over both clusters) of the intracluster...