Given an $m \times n$ matrix $A$ with positive and negative entries, consider the problem of maximizing the expression $\sum_{i,j} x_i y_j a_{ij}$ subject to the constraints $x_i, \, y_j = \pm 1$. It was shown by N. Alon and A. Naor in SIAM J. Comput. vol. 35, 2006 that this problem is MAX-SNP hard, and they gave a relaxation approach that uses semidefinite programming and that gets within 0.56 of the maximum.
On the other hand it is immediate that if $A = a b^t$ has rank 1, where $a, \ b$ are column vectors, then $x_i = sign\ a_i, \ y_j = sign \ b_j$ is the optimum.
My question is whether there are also "better" approaches if $A$ has merely low rank > 1.
