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

Full description

Saved in:
Bibliographic Details
Published in:Journal of combinatorial optimization 2013-07, Vol.26 (1), p.1-9
Main Authors: Polyakovskiy, Sergey, Spieksma, Frits C. R., Woeginger, Gerhard J.
Format: Article
Language:English
Subjects:
Combinatorics
Convex and Discrete Geometry
Mathematical Modeling and Industrial Mathematics
Mathematics
Mathematics and Statistics
Operations Research/Decision Theory
Optimization
Theory of Computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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).
ISSN:1382-6905
1573-2886
DOI:10.1007/s10878-011-9426-y