Polynomially solvable special cases of the quadratic bottleneck assignment problem

Quadratic bottleneck assignment problems (QBAP) are obtained by replacing the addition of cost terms in the objective function of a quadratic (sum) assignment problem by taking their maximum. Since the QBAP is an NP\mathcal{NP}-hard problem, polynimially solvable special cases of the QBAP are of interest. In this paper we specify conditions on the cost matrices of QBAP leading to special cases which can be solved to optimality in polynomial time. In particular, the following three cases are discussed: (i) any permutation is optimal (constant QBAP), (ii) a certain specified permutation is optimal (constant permutation QBAP) and (iii) the solution can be found algorithmically by a polynomial algorithm. Moreover, the max-cone of bottleneck Monge matrices is investigated, its generating matrices are identified and it is used as a tool in proving polynomiality results.