On the Complexity of Some Euclidean
Optimal Summing Problems

A. V. Eremeev^{a, b}, A. V. Kel’manov^{c, d}, and A. V. Pyatkin^{c, d}

Presented by Academician of the RAS Yu.G. Evtushenko December 15, 2015

Received December 17, 2015

Abstract—The complexity status of several discrete optimization problems concerning the search for a subset
of a finite set of Euclidean points (vectors) is analyzed. In the considered problems, the aim is to minimize
objective functions depending either only on the norm of the sum of the elements from the subset or on this
norm and the cardinality of the subset. It is proved that, if the dimension of the space is part of the input, then
all analyzed problems are strongly NP-hard and, if the space dimension is fixed, then these problems are NP-
hard even for dimension 2 (on a plane). It is shown that, if the coordinates of the input points are integer, then
all the problems can be solved in pseudopolynomial time in the case of a fixed space dimension.

DOI: 10.1134/S1064562416030157

Pleiades Publishing home page | journal home page | top

If you have any problems with this server, contact webmaster.