The three-dimensional matching problem in Kalmanson matrices
Files
(Published version)
Date
2013
Authors
Polyakovskiy, S.
Spieksma, F.
Woeginger, G.
Editors
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Journal article
Citation
Journal of Combinatorial Optimization, 2013; 26(1):1-9
Statement of Responsibility
Sergey Polyakovskiy, Frits C. R. Spieksma, Gerhard J. Woeginger
Conference Name
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).
School/Discipline
Dissertation Note
Provenance
Description
Access Status
Rights
© The Author(s) 2011