On Finding Minimum Cardinality Subset of Vectors with a Constraint on the Sum of Squared Euclidean Pairwise Distances

摘要

In this paper, we consider the problem of finding a minimum cardinality subset of vectors, given a constraint on the sum of squared Euclidean distances between all vectors of the chosen subset. This problem is closely related to the well-known Maximum Diversity Problem. The main difference consists in swapping the constraint with the optimization criterion. We prove that the problem is NP-hard in the strong sense. An exact algorithm for solving this problem is proposed. The algorithm has a pseudo-polynomial time complexity in the special case of the problem, where the dimension of the space is bounded from above by a constant and the input data are integer.