Planar 3-dimensional assignment problems with Monge-like cost arrays

Abstract

Given an $n\times n\times p$ cost array $C$ we consider the problem $p$-P3AP which consists in finding $p$ pairwise disjoint permutations ${\phi }_1,{\phi }_2,\dots ,{\phi }_p$ of $\{1,\dots ,n\}$ such that ${\sum }_{k=1}^p{\sum }_{i=1}^n{c}_{i{\phi }_k(i)k}$ is minimized. For the case $p=n$ the planar 3-dimensional assignment problem P3AP results. Our main result concerns the $p$-P3AP on cost arrays $C$ that are layered Monge arrays. In a layered Monge array all $n\times n$ matrices that result from fixing the third index $k$ are Monge matrices. We prove that the $p$-P3AP and the P3AP remain NP-hard for layered Monge arrays. Furthermore, we show that in the layered Monge case there always exists an optimal solution of the $p$-3PAP which can be represented as matrix with bandwidth $\le 4p-3$. This structural result allows us to provide a dynamic programming algorithm that solves the $p$-P3AP in polynomial time on layered Monge arrays when $p$ is fixed.

16 pages, appendix will follow in v2

References in corpus (1)

• The constant objective value property for combinatorial optimization problems