English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider the bipartite unconstrained 0-1 quadratic programming problem(BQP01) which is a generalization of the well studied unconstrained 0-1quadratic programming problem (QP01). BQP01 has numerous applications and theproblem 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 inpolynomial time. When $Q$ is of rank one, we provide an $O(n\log n)$ algorithmand 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 solvablein $O(mn\log n)$ time. By restricting $m=O(\log n),$ we obtain yet anotherpolynomially solvable case of BQP01 but the problem remains MAX SNP hard if$m=O(\sqrt[k]{n})$ for a fixed $k$. Finally, if the minimum number of rows andcolumns to be deleted from $Q$ to make the remaining matrix non-negative is$O(\log n)$ then we show that BQP01 polynomially solvable but it is NP-hard ifthis number is $O(\sqrt[k]{n})$ for any fixed $k$.  Keywords: quadratic programming, 0-1 variables, polynomial algorithms,complexity, pseudo-Boolean programming.

The bipartite unconstrained 0-1 quadratic programming problem: polynomially solvable cases