2
$\begingroup$

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$.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ What is $q_i??$ $\endgroup$
    – Igor Rivin
    Commented Apr 4, 2012 at 6:08
  • $\begingroup$ Sorry, I meant $q_{1i}$, the $i$-th entry of the largest eigenvector $q_1$. The question is now edited. $\endgroup$
    – Woland
    Commented Apr 4, 2012 at 19:09

1 Answer 1

Reset to default
4
$\begingroup$

The reference where all is revealed is Bodlaender, Gritzman, Klee, Van Leeuwen

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .