The three-dimensional matching problem in Kalmanson matrices

S. Polyakovskiy, F.C.R. Spieksma, G.J. Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

7 Citations (Scopus)
1 Downloads (Pure)


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).
Original languageEnglish
Pages (from-to)1-9
JournalJournal of Combinatorial Optimization
Issue number1
Publication statusPublished - 2013


Dive into the research topics of 'The three-dimensional matching problem in Kalmanson matrices'. Together they form a unique fingerprint.

Cite this