Abstract:
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.
Fulltext:
PDF file (373 kB)