In this paper we study the complexity and domination analysis in the context of the \emph{ bipartite quadratic assignment problem}. Two variants of the problem, denoted by BQAP1 and BQAP2, are investigated. A formula for calculating the average objective function value $\mathcal{ A}$ of all solutions is presented whereas computing the median objective function value is shown to be NP-hard. We show that any heuristic algorithm that produces a solution with objective function value at most $\mathcal{ A}$ has the domination ratio at least $\frac{ 1}{ mn}$. Analogous results for the standard \emph{ quadratic assignment problem} is an open question. We show that computing a solution whose objective function value is no worse than that of $n^mm^n-{ \lceil\frac{ n}{ \alpha}\rceil}^{ \lceil\frac{ m}{ \alpha}\rceil}{ \lceil\frac{ m}{ \alpha}\rceil}^{ \lceil\frac{ n}{ \alpha}\rceil}$ solutions of BQAP1 or $m^mn^n-{ \lceil\frac{ m}{ \alpha}\rceil}^{ \lceil\frac{ m}{ \alpha}\rceil}{ \lceil\frac{ n}{ \alpha}\rceil}^{ \lceil\frac{ n}{ \alpha}\rceil}$ solutions of BQAP2, is NP-hard for any fixed natural numbers $a$ and $b$ such that $\alpha=\frac{ a}{ b}>1$. However, a solution with the domination number $\Omega(m^{ n-1}n^{ m-1}+m^{ n+1}n+mn^{ m+1})$ for BQAP1 and $\Omega(m^{ m-1}n^{ n-1}+m^2n^{ n}+m^mn^2)$ for BQAP2, can be found in $O(m^3n^3)$ time.

Categories: math.OC

Average value of solutions of the bipartite quadratic assignment problem and linkages to domination analysis