NP-Hardness of Some Euclidean Problems of Partitioning a Finite Set of Points

Problems of partitioning a finite set of Euclidean points (vectors) into clusters are considered. The criterion is to minimize the sum, over all clusters, of (1) squared norms of the sums of cluster elements normalized by the cardinality, (2) squared norms of the sums of cluster elements, and (3) norms of the sum of cluster elements. It is proved that all these problems are strongly NP-hard if the number of clusters is a part of the input and are NP-hard in the ordinary sense if the number of clusters is not a part of the input (is fixed). Moreover, the problems are NP-hard even in the case of dimension 1 (on a line).     

On complexity of a choice problem of the vector subset with the maximum sum length

The choice problem of the vector subset with the maximum sum length is considered. In the case of fixed space dimension, this problem is polynomially solvable. The NP-completeness of the problem is proved if the space dimension is not fixed.     

The problem of finding a subset of vectors with the maximum total weight

The NP-hardness is proved for the discrete optimization problems connected with maximizing the total weight of a subset of a finite set of vectors in Euclidean space, i.e., the Euclidean norm of the sum of the members. Two approximation algorithms are suggested, and the bounds for the relative error and time complexity are obtained. We give a polynomial approximation scheme in the case of a fixed dimension and distinguished a subclass of problems solvable in pseudopolynomial time. The results obtained are useful for solving the problem of choice of a fixed number of subsequences from a numerical sequence with a given number of quasiperiodical repetitions of the subsequence.