Maximum magnitude subset sum

Let $z_1,z_2,\dots,z_N$ be vectors from $\mathbb Z^m$ for some $m$. The problem is:

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.

I am most interested in cases where $m$ is small, not much more than $2$, and $N$ is large, potentially $1000$s.

I would be surprised if this problem had not previously been studied. Has anybody seen it before? Does it have a name?

edited Nov 13 at 5:05

asked Nov 13 at 0:41

Robby McKilliam
697●5●8

	A starting point would be to start looking at work on column subset selection, see e.g., arxiv.org/pdf/1201.0127 – S. Sra Nov 13 at 1:57
	You should probably have the vectors be from $\mathbb{Z}^m$ (to avoid there being no computable solution). – Ricky Demer Nov 13 at 3:20
	@Ricky Thanks, I've made that change. – Robby McKilliam Nov 13 at 3:53
	@Gerry My bad, I obviously mean positive integer! Fixed. – Robby McKilliam Nov 13 at 5:05

Browse other questions tagged combinatorial-optimizatio or ask your own question.

question feed