Complexity and Approximation of Finding the Longest Vector Sum

详细

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(logn)\), a randomized polynomial-time approximation scheme is proposed.