On the complexity of some Euclidean optimal summing problems
- Authors: Eremeev A.V.1,2, Kel’manov A.V.3,4, Pyatkin A.V.3,4
-
Affiliations:
- Omsk Branch of Sobolev Institute of Mathematics, Siberian Branch
- Omsk State University
- Sobolev Institute of Mathematics, Siberian Branch
- Novosibirsk State University
- Issue: Vol 93, No 3 (2016)
- Pages: 286-288
- Section: Mathematics
- URL: https://journals.rcsi.science/1064-5624/article/view/223742
- DOI: https://doi.org/10.1134/S1064562416030157
- ID: 223742
Cite item
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.
About the authors
A. V. Eremeev
Omsk Branch of Sobolev Institute of Mathematics, Siberian Branch; Omsk State University
Author for correspondence.
Email: eremeev@ofim.oscsbras.ru
Russian Federation, ul. Pevtsova 13, Omsk, 644099; pr. Mira 55a, Omsk, 630077
A. V. Kel’manov
Sobolev Institute of Mathematics, Siberian Branch; Novosibirsk State University
Email: eremeev@ofim.oscsbras.ru
Russian Federation, pr. Akademika Koptyuga 4, Novosibirsk, 630090; ul. Pirogova 2, Novosibirsk, 630090
A. V. Pyatkin
Sobolev Institute of Mathematics, Siberian Branch; Novosibirsk State University
Email: eremeev@ofim.oscsbras.ru
Russian Federation, pr. Akademika Koptyuga 4, Novosibirsk, 630090; ul. Pirogova 2, Novosibirsk, 630090