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$
  • 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 Apr 28 '16 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 Apr 29 '16 at 5:56
  • $\begingroup$ Thanks. Do you think, there might exist a randomized algorithm/FPT to solve this optimization problem. $\endgroup$ – Vadapalli Adithya May 6 '16 at 9:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.