Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
    
A starting point would be to start looking at work on column subset selection, see e.g., arxiv.org/pdf/1201.0127 –  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
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.