Approximability of the Problem of Finding a Vector Subset with the Longest 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 a \), where α = 2/π, and if P ≠ NP then there are no polynomial algorithms with better accuracy. It is shown that, in the case of the ℓ_p spaces, the problem is APX-complete if p ∈ [1, 2] and not approximable with constant accuracy if P ≠ NP and p ∈ (2,∞).