Consider the problem:
$\textrm{max}\;\; x^T Q x$
subject to $||x||_\infty \leq 1$, where $Q$ is a positive definite matrix.
I believe this problem is NP-hard (although I have only found hardness results for positive semi-definite matrices).
Consider now the following algorithm. Let $q_1$ be the largest eigenvector of $Q$. Let the solution $x$ be defined by $x_i = \textrm{sign}(q_{1i})$.
When does this algorithm fail? So far, I have looked for examples in 2d or 3d, and have not found any.
Note that the intuition here is that $x$ should be as close as possible to $q_1$.
