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?

up vote 1 down vote accepted

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.

  • I'm unclear on how this argument works or what algorithm you're proposing. Could you elaborate? – Jake Dec 5 '17 at 3:05
  • Oh I get it now. That took a bit of unpacking. You logically rotate the x-axis and consider each partition above and below the x-axis. That yields a O(n^2) algorithm. – Jake Dec 5 '17 at 3:09

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.