Approximability of the problem of finding a~vector subset with the longest sum

V. V. Shenmaier

Diskretnyj analiz i issledovanie operacij, Tome 25 (2018) no. 4, pp. 131-148

Résumé

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.

Détail

Keywords: sum vector, search for a vector subset, approximation algorithm, inapproximability bound.