Approximability of the problem of finding a~vector subset with the longest sum
Diskretnyj analiz i issledovanie operacij, Tome 25 (2018) no. 4, pp. 131-148
Voir la notice de l'article provenant de la source Math-Net.Ru
We answer the question of existence of polynomial-time constant-factor approximation algorithms for the space of nonfixed dimension. We prove that, in Euclidean space the problem is solvable in polynomial time with accuracy $\sqrt\alpha$, where $\alpha=2/\pi$, and if $\mathrm P\neq\mathrm{NP}$ then there are no polynomial algorithms with better accuracy. It is shown that, in the case of the $\ell_p$ spaces, the problem is APX-complete if $p\in[1,2]$ and not approximable with constant accuracy if $\mathrm P\neq\mathrm{NP}$ and $p\in(2,\infty)$. Tab. 1, bibliogr. 21.
Keywords:
sum vector, search for a vector subset, approximation algorithm, inapproximability bound.
@article{DA_2018_25_4_a8,
author = {V. V. Shenmaier},
title = {Approximability of the problem of finding a~vector subset with the longest sum},
journal = {Diskretnyj analiz i issledovanie operacij},
pages = {131--148},
publisher = {mathdoc},
volume = {25},
number = {4},
year = {2018},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/DA_2018_25_4_a8/}
}
TY - JOUR AU - V. V. Shenmaier TI - Approximability of the problem of finding a~vector subset with the longest sum JO - Diskretnyj analiz i issledovanie operacij PY - 2018 SP - 131 EP - 148 VL - 25 IS - 4 PB - mathdoc UR - http://geodesic.mathdoc.fr/item/DA_2018_25_4_a8/ LA - ru ID - DA_2018_25_4_a8 ER -
V. V. Shenmaier. Approximability of the problem of finding a~vector subset with the longest sum. Diskretnyj analiz i issledovanie operacij, Tome 25 (2018) no. 4, pp. 131-148. http://geodesic.mathdoc.fr/item/DA_2018_25_4_a8/