1
$\begingroup$

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?

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

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.