# Non-Linear Programming with \min operator in the constraint

Can the following non-linear program be solved in polynomial time? $c_{ij}$'s are constants and known. Each $c_{ij}$ is either -1 or 1.

\begin{align} \text{maximize } &\sum_{i,j=1}^{m,n} c_{ij} \gamma_{ij} \notag\\ \text{subject to: }& \notag\\ & \gamma_{ij} = \min\{1, \sum_{k = 1}^{K}{x_{ik}y_{jk} }\} && \forall i,j\\ & 0 \le x_{ik}, y_{jk} \le 1 && \forall i,j,k \end{align}

• Should $mn$ be replaced with ​ $m\hspace{.02 in},\hspace{-0.02 in}n$ ? ​ ​ ​ (If no, then I don't know what that sum means.) ​ ​ ​ ​ ​ ​ ​ ​ – user6973 Apr 28 '16 at 10:14
• Seems unlikely. Even for $K=1$, deciding whether a given instance has value at least $\ell$ is equivalent to the following problem: given a bipartite graph $G=(V,W,E)$, decide whether it has an induced subgraph $G'=(V',W',E')$ with at least $\ell$ more edges than non-edges (that is, $2|E'| - |V'|\,|W'| \ge \ell$). I'd guess that is NP-hard. – Neal Young Apr 29 '16 at 5:56
• Thanks. Do you think, there might exist a randomized algorithm/FPT to solve this optimization problem. – Vadapalli Adithya May 6 '16 at 9:28