2
$\begingroup$

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}

$\endgroup$
3
  • 1
    $\begingroup$ 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.) ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$
    – user6973
    Commented Apr 28, 2016 at 10:14
  • 1
    $\begingroup$ 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. $\endgroup$
    – Neal Young
    Commented Apr 29, 2016 at 5:56
  • $\begingroup$ Thanks. Do you think, there might exist a randomized algorithm/FPT to solve this optimization problem. $\endgroup$ Commented May 6, 2016 at 9:28

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.