@Article{Punnen2015,
  Title                    = {The bipartite unconstrained 0-1 quadratic programming problem: polynomially solvable cases},
  Author                   = {Punnen, Abraham P and Sripratak, Piyashat and Karapetyan, Daniel},
  Journal                  = {Discrete Applied Mathematics},
  Year                     = {2015},
  Pages                    = {1--10},
  Volume                   = {193},
  Abstract                 = {We consider the bipartite unconstrained 0-1 quadratic programming problem (BQP01) which is a generalization of the well studied unconstrained 0-1 quadratic programming problem (QP01). BQP01 has numerous applications and the problem is known to be MAX SNP hard. We show that if the rank of an associated $m\times n$ cost matrix $Q=(q_{ij})$ is fixed, then BQP01 can be solved in polynomial time. When $Q$ is of rank one, we provide an $O(n\log n)$ algorithm and this complexity reduces to $O(n)$ with additional assumptions. Further, if $q_{ij}=a_i+b_j$ for some $a_i$ and $b_j$, then BQP01 is shown to be solvable in $O(mn\log n)$ time. By restricting $m=O(\log n),$ we obtain yet another polynomially solvable case of BQP01 but the problem remains MAX SNP hard if $m=O(\sqrt[k]{n})$ for a fixed $k$. Finally, if the number of negative entries in $Q$ is fixed, BQP01 is shown to be polynomially solvable whereas it is NP-hard if this number is $O(\sqrt[k]{n})$ for a fixed $k$.},
  Arxivid                  = {1212.3736},
  DOI                      = {10.1016/j.dam.2015.04.004},
  Keywords                 = {0-1 variables,BQP,complexity,polynomial algorithms,pseudo-boolean programming,quadratic programming},
  Mendeley-tags            = {BQP}
}