Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/87190
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Journal article |
Title: | The three-dimensional matching problem in Kalmanson matrices |
Author: | Polyakovskiy, S. Spieksma, F. Woeginger, G. |
Citation: | Journal of Combinatorial Optimization, 2013; 26(1):1-9 |
Publisher: | Springer US |
Issue Date: | 2013 |
ISSN: | 1382-6905 1573-2886 |
Statement of Responsibility: | Sergey Polyakovskiy, Frits C. R. Spieksma, Gerhard J. Woeginger |
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). |
Keywords: | Computational complexity; Combinatorial optimization; Tractable case |
Rights: | © The Author(s) 2011 |
DOI: | 10.1007/s10878-011-9426-y |
Published version: | http://dx.doi.org/10.1007/s10878-011-9426-y |
Appears in Collections: | Aurora harvest 7 Computer Science publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
hdl_87190.pdf | Published version | 345.54 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.