Complexity and Approximation of the Longest Vector Sum Problem

摘要

Given a set of n vectors in a d-dimensional normed space, consider the problem of finding a subset with the largest length of the sum vector. We prove that, for any l_p norm, p ∈ [1,∞), the problem is hard to approximate within a factor better than min{α~(1/p), {the square root of}α}, where α = 16/17. In the general case, we show that the cardinality-constrained version of the problem is hard for approximation factors better than 1 - 1/e and is W[2]-hard with respect to the cardinality of the solution. For both original and cardinality-constrained problems, we propose a randomized (1 - ε)-approximation algorithm that runs in polynomial time when the dimension of space is O(log n). The algorithm has a linear time complexity for any fixed d and ε ∈ (0, 1).