1
$\begingroup$

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?

$\endgroup$
0

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I'm unclear on how this argument works or what algorithm you're proposing. Could you elaborate? $\endgroup$
    – Jake
    Dec 5, 2017 at 3:05
  • $\begingroup$ 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. $\endgroup$
    – Jake
    Dec 5, 2017 at 3:09

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