# Hardness of checking maximal magnitude of a sum of a subset of vectors

The problem I wish to solve is the following:

Given a set $V \subset \mathbb{Z}^2$ find the set $S \subset V$ such that $|\sum_{v \in S} v|$ is maximal.

By simply enumerating subsets we can solve this problem in $O(2^n)$. This problem feels a lot like the euclidian traveling salesmen problem to me but I can't quite make it fit. I've tried other numerical optimization techniques like giving each vector an associated scalar variable, the idea being that if the variable was 0 then you'd exclude the associated vector it and if it was 1 then you'd include it. Then the goal is to find an assignment of the variables that maximizes this (I used Lagrange's method). That pretty much just got me back to a clearly equivalent problem that I had no more hope of solving efficiently. I can't seem to find any way to do this any faster. Additionally, I'm having trouble concluding that it's NP-hard but it's my bet that it is. For such a simple problem I'd imagine it's been considered before.

Is this problem known NP-hard? Is there a reduction I just haven't seen yet? Is there some efficient algorithm I just haven't seen?

I suppose you are talking about the euclidean norm. Consider the optimal solution $S$ and let $w=\sum_{v\in S}v$, and we assume there's no zero vector in $V$.
For any $v\notin S$, it must holds $v\cdot w<0$, otherwise $\|w+v\|^2\geq \|w\|^2+\|v\|^2>\|w\|^2$. Similarly for $v\in S$ it holds $v\cdot w>0$, otherwise $\|w-v\|>\|w\|$.
That means $S$ is exactly determined by the direction of $w$. You can exhaust the possibilities by sorting the polar angles of the vectors, and rotate the orthogonal line of $w$ which has only $n$ essentially different partitions.