El problema es el siguiente
Dado $v_1, \, v_2, \, \ldots, \, v_n \in \mathbb R^m$; encontrar $\epsilon_1, \, \epsilon_2, \, \ldots, \, \epsilon_n \in \{0,1\}$ tal que $$\left\vert \sum_{i=1}^n (-1)^{\epsilon_i} v_i \right\vert = \max$$ donde $\vert \cdot\vert $ denota la norma Euclídea.
I. e. lo que queremos es maximizar la longitud de una suma de vectores, bajo la restricción de que para cada vector debemos utilizar el vector propio o $(-1)$ veces este vector.
Este vino de alguna aplicación y me preguntó si yo sabía cómo obtener una solución de hace algún tiempo. No veo un algoritmo eficiente y dado que el número de vectores normalmente era lo suficientemente pequeña, podría ser resuelto por simplemente ir a través de todas las posibilidades.
Lo pensé de nuevo, el día de hoy. Y realmente el problema parece que no puede ser un buen algoritmo eficiente para resolver - al menos mejor que el $\Theta(2^n)$.
Todavía no ser capaz de encontrar uno, quería preguntar si alguien de aquí podría encontrar una buena solución!
Algo que no funciona:
- El fin de los vectores de longitud: $|v_1|\ge |v_2|\ge \dots \ge |v_n|$
- Después de haber encontrado una máxima vector de combinación de la $v = \sum \pm v_i$$v_1, \, v_2, \, \ldots, \, v_k$, elija el signo de $v_{k+1}$, de modo que se maximiza la duración de la $v \pm v_{k+1}$.
Un contraejemplo es dado por $\begin{pmatrix} 3\\ 2\end{pmatrix},\, \begin{pmatrix} -2\\ 3\end{pmatrix},\, \begin{pmatrix} 2\\ 3\end{pmatrix}$. La combinación de los dos primeros vectores obtenemos $$\begin{pmatrix} 1\\ 5\end{pmatrix} \quad \text{or}\quad \begin{pmatrix} 5\\ -1\end{pmatrix}$$ ambos de los cuales tienen la misma longitud. Sin embargo, si elegimos la primera combinación que podemos obtener $\begin{pmatrix} 3\\ 8\end{pmatrix}$, mientras que para la segunda combinación de $\begin{pmatrix} 7\\ 2\end{pmatrix}$ es lo mejor que podemos hacer.
Siéntase libre de compartir tus pensamientos! Gracias. =)
