MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
A starting point would be to start looking at work on column subset selection, see e.g., – Suvrit Nov 13 '12 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 '12 at 3:20
@Ricky Thanks, I've made that change. – Robby McKilliam Nov 13 '12 at 3:53
@Gerry My bad, I obviously mean positive integer! Fixed. – Robby McKilliam Nov 13 '12 at 5:05

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.