The three-dimensional matching problem in Kalmanson matrices

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).

Publication year:2013

BOF-keylabel:yes

IOF-keylabel:yes

BOF-publication weight:1

CSS-citation score:1

Authors:International

Authors from:Higher Education

Accessibility:Closed