Geodesic
On the complexity and approximability of some Euclidean optimal summing problems
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 56 (2016) no. 10, pp. 1831-1836

Voir la notice de l'article provenant de la source Math-Net.Ru

The complexity status of several well-known discrete optimization problems with the direction of optimization switching from maximum to minimum is analyzed. The task is to find a subset of a finite set of Euclidean points (vectors). In these problems, the objective functions depend 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 a part of the input, then all these problems are strongly $\mathrm{NP}$-hard. Additionally, it is shown that, if the space dimension is fixed, then all the problems are $\mathrm{NP}$-hard even for dimension $2$ (on a plane) and there are no approximation algorithms with a guaranteed accuracy bound for them unless $\mathrm{P=NP}$. 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. 
@article{ZVMMF_2016_56_10_a13,
     author = {A. V. Eremeev and A. V. Kel'manov and A. V. Pyatkin},
     title = {On the complexity and approximability of some {Euclidean} optimal summing problems},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {1831--1836},
     publisher = {mathdoc},
     volume = {56},
     number = {10},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2016_56_10_a13/}
}
TY  - JOUR
AU  - A. V. Eremeev
AU  - A. V. Kel'manov
AU  - A. V. Pyatkin
TI  - On the complexity and approximability of some Euclidean optimal summing problems
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2016
SP  - 1831
EP  - 1836
VL  - 56
IS  - 10
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2016_56_10_a13/
LA  - ru
ID  - ZVMMF_2016_56_10_a13
ER  - 
%0 Journal Article
%A A. V. Eremeev
%A A. V. Kel'manov
%A A. V. Pyatkin
%T On the complexity and approximability of some Euclidean optimal summing problems
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2016
%P 1831-1836
%V 56
%N 10
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ZVMMF_2016_56_10_a13/
%G ru
%F ZVMMF_2016_56_10_a13
A. V. Eremeev; A. V. Kel'manov; A. V. Pyatkin. On the complexity and approximability of some Euclidean optimal summing problems. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 56 (2016) no. 10, pp. 1831-1836. http://geodesic.mathdoc.fr/item/ZVMMF_2016_56_10_a13/