Maximum magnitude subset sum - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T17:35:25Z http://mathoverflow.net/feeds/question/112237 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/112237/maximum-magnitude-subset-sum Maximum magnitude subset sum Robby McKilliam 2012-11-13T00:41:12Z 2012-11-13T05:05:59Z <p>Let $z_1,z_2,\dots,z_N$ be vectors from $\mathbb Z^m$ for some $m$. The problem is:</p> <p>Given a positive integer $p$, find the subset $A_p \subset \{ 1,2,\dots,N \}$ of size $|A_p| = p$ such that $$\|\sum_{i \in A_p} z_i \|$$ is maximized, where $\|\cdot\|$ is the Euclidean norm.</p> <p>I am most interested in cases where $m$ is small, not much more than $2$, and $N$ is large, potentially $1000$s.</p> <p>I would be surprised if this problem had not previously been studied. Has anybody seen it before? Does it have a name?</p>