Skip to main content
2 of 2
added 22 characters in body
Michael Hardy
  • 1
  • 12
  • 85
  • 126

Sum of k vectors with largest possible norm

Suppose I have a family of $n$ vectors in $\mathbb{R}^d$: $v_1,\dots,v_n.$ Is there a poly-time algorithm that computes a subset $S\subset [n]:=\{1,\dots,n\}$ of size $1\leq k\leq n$ for which the (Euclidean) norm of the sum $\|\sum_{i\in S}v_i\|_2$ is as large as possible? That is, I am looking for an algorithm that computes: $$\operatorname*{arg max}_{S\subset [n],\# S=k} \left\|\sum_{i\in S}v_i\right\|_2.$$

References for exact methods, approximate solutions and/or hardness results would be most welcome.