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?

Improve this question
$\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
    Commented 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
    Commented Nov 13, 2012 at 3:20
  • $\begingroup$ @Ricky Thanks, I've made that change. $\endgroup$
    – Robby McKilliam
    Commented Nov 13, 2012 at 3:53
  • $\begingroup$ @Gerry My bad, I obviously mean positive integer! Fixed. $\endgroup$
    – Robby McKilliam
    Commented Nov 13, 2012 at 5:05

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .