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

We study domination analysis of algorithms for the bipartite quadratic assignment problem. A formula for the average objective function value of solutions is presented, whereas computing the median objective function value is shown to be NP-hard. An upper bound on the domination ratio of any polynomial time heuristic is given. Also, we show that heuristics that produce no worse than the average solutions have domination ratio at least 1mn. Heuristics with improved domination ratio are also presented.