Abstract:
The problem under study is, given a finite set of vectors in a normed vector space, find a subset which maximizes the norm of the vector sum. For each $\ell_p$ norm, $p\in[1,\infty)$, the problem is proved to have an inapproximability bound in the class of polynomial-time algorithms. For an arbitrary normed space of dimension $O(\log n)$, a randomized polynomial-time approximation scheme is proposed.