Hardness of maximizing $x^TAy$ with $\{-1,1\}$ entries

Question

My question concerns the NP-hardness of the following discrete optimization problem:

Given a matrix $A \in \{ \pm 1 \}^{m\times n}$,

$$\begin{array}{ll} \underset{x \in \{ \pm 1 \}^m ,\, y \in \{ \pm 1 \}^n}{\text{maximize}} & x^T A \, y\end{array}$$

Is this problem known to be NP-hard?

If $A$ can also have zero entries, then it is NP-hard. I doubt this is really necessary, but I don't have an immediate argument for this. — Jason Gaitonde, Jun 23, 2021 at 19:24

Kristoffer Arnsfelt Hansen · Accepted Answer · 2021-06-27 14:14:18Z

6

NP-hardness is proved by Roth and Viswanathan in the paper On the hardness of decoding the gale-berlekamp code

answered Jun 27, 2021 at 14:14

4,1292 gold badges26 silver badges36 bronze badges

$\begingroup$ Thank you very much! I also found a proof in doi.org/10.1287/moor.2017.0895. $\endgroup$
– W. Mapa
Jun 28, 2021 at 14:13
$\begingroup$ Yes - They appear to have rediscovered the proof of Roth and Viswanathan. $\endgroup$
– Kristoffer Arnsfelt Hansen
Jun 29, 2021 at 21:46

Add a comment |

1 Answer 1