On the complexity of some Euclidean optimal summing problems
- Авторлар: Eremeev A.1,2, Kel’manov A.3,4, Pyatkin A.3,4
-
Мекемелер:
- Omsk Branch of Sobolev Institute of Mathematics, Siberian Branch
- Omsk State University
- Sobolev Institute of Mathematics, Siberian Branch
- Novosibirsk State University
- Шығарылым: Том 93, № 3 (2016)
- Беттер: 286-288
- Бөлім: Mathematics
- URL: https://journals.rcsi.science/1064-5624/article/view/223742
- DOI: https://doi.org/10.1134/S1064562416030157
- ID: 223742
Дәйексөз келтіру
Аннотация
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.
Авторлар туралы
A. Eremeev
Omsk Branch of Sobolev Institute of Mathematics, Siberian Branch; Omsk State University
Хат алмасуға жауапты Автор.
Email: eremeev@ofim.oscsbras.ru
Ресей, 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
Ресей, 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
Ресей, pr. Akademika Koptyuga 4, Novosibirsk, 630090; ul. Pirogova 2, Novosibirsk, 630090