The problem is the following
Given $v_1, \, v_2, \, \ldots, \, v_n \in \mathbb R^m$; find $\epsilon_1, \, \epsilon_2, \, \ldots, \, \epsilon_n \in \{0,1\}$ such that $\left\vert \sum_{i=1}^n (-1)^{\epsilon_i} v_i \right\vert = \max$ where $\vert \cdot\vert $ denotes the Euclidean norm.
I.e. we want to maximize the length of a sum of vectors, under the restriction that for every vector we must use either the vector itself or $(-1)$ times this vector.
This came from some application and I was asked whether I knew how to obtain a solution some time ago. I didn't see an efficient algorithm and since the number of vectors typically was sufficiently small, it could be solved by simply going through all possibilities.
I thought about it again, today. And the problem really looks like there might be a nice efficient algorithm to solve it - at least better than $\Theta(2^n)$.
Still not being able to find one, I wanted to ask whether someone here could figure out a neat solution!
Something that doesn't work:
- Order the vectors by length: $|v_1|\ge |v_2|\ge \dots \ge |v_n|$
- Having found a maximal vector-combination $v = \sum \pm v_i$ from $v_1, \, v_2, \, \ldots, \, v_k$, choose the sign of $v_{k+1}$ so that it maximizes the length of $v \pm v_{k+1}$.
A counterexample is given by $\begin{pmatrix} 3\\ 2\end{pmatrix},\, \begin{pmatrix} -2\\ 3\end{pmatrix},\, \begin{pmatrix} 2\\ 3\end{pmatrix}$. Combining the first two vectors we get $\begin{pmatrix} 1\\ 5\end{pmatrix} \quad \text{or}\quad \begin{pmatrix} 5\\ -1\end{pmatrix}$ both of which have the same length. However, if we choose the first combination we can get $\begin{pmatrix} 3\\ 8\end{pmatrix}$ whereas for the second combination $\begin{pmatrix} 7\\ 2\end{pmatrix}$ is the best we can do.
Feel free to share your thoughts! Thanks. =)