Journal of Combinatorial Optimization vol:26 issue:1 pages:1-9
We investigate the computational complexity of several special cases of the three-dimensional matching problem where the costs are decomposable and determined by a so-called Kalmanson matrix. For the minimization version we develop an efficient polynomial time algorithm that is based on dynamic programming. For the maximization version, we show that there is a universally optimal matching (whose
structure is independent of the particular Kalmanson matrix).