On the complexity of some Euclidean optimal summing problems
- Autores: Eremeev A.1,2, Kel’manov A.3,4, Pyatkin A.3,4
-
Afiliações:
- Omsk Branch of Sobolev Institute of Mathematics, Siberian Branch
- Omsk State University
- Sobolev Institute of Mathematics, Siberian Branch
- Novosibirsk State University
- Edição: Volume 93, Nº 3 (2016)
- Páginas: 286-288
- Seção: Mathematics
- URL: https://journals.rcsi.science/1064-5624/article/view/223742
- DOI: https://doi.org/10.1134/S1064562416030157
- ID: 223742
Citar
Resumo
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.
Sobre autores
A. Eremeev
Omsk Branch of Sobolev Institute of Mathematics, Siberian Branch; Omsk State University
Autor responsável pela correspondência
Email: eremeev@ofim.oscsbras.ru
Rússia, ul. Pevtsova 13, Omsk, 644099; pr. Mira 55a, Omsk, 630077
A. Kel’manov
Sobolev Institute of Mathematics, Siberian Branch; Novosibirsk State University
Email: eremeev@ofim.oscsbras.ru
Rússia, pr. Akademika Koptyuga 4, Novosibirsk, 630090; ul. Pirogova 2, Novosibirsk, 630090
A. Pyatkin
Sobolev Institute of Mathematics, Siberian Branch; Novosibirsk State University
Email: eremeev@ofim.oscsbras.ru
Rússia, pr. Akademika Koptyuga 4, Novosibirsk, 630090; ul. Pirogova 2, Novosibirsk, 630090