polyakovskiy-threedimensional-2013.pdf (354.77 kB)
The three-dimensional matching problem in Kalmanson matrices
journal contribution
posted on 2013-07-01, 00:00 authored by Sergey PolyakovskiySergey Polyakovskiy, F C R Spieksma, G J WoegingerWe 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).
History
Journal
Journal of combinatorial optimizationVolume
26Issue
1Pagination
1 - 9Publisher
SpringerLocation
New York, N.Y.Publisher DOI
Link to full text
ISSN
1382-6905eISSN
1573-2886Language
engPublication classification
C Journal article; C1.1 Refereed article in a scholarly journalCopyright notice
2011, The AuthorsUsage metrics
Categories
No categories selectedKeywords
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC