The three-dimensional matching problem in Kalmanson matrices

Research output: Contribution to journalArticleAcademicpeer-review

7 Citations (Scopus)
1 Downloads (Pure)

Abstract

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
Volume26
Issue number1
DOIs
Publication statusPublished - 2013

Fingerprint

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

Cite this