Deakin University
Browse
polyakovskiy-threedimensional-2013.pdf (354.77 kB)

The three-dimensional matching problem in Kalmanson matrices

Download (354.77 kB)
Version 2 2024-06-04, 14:21
Version 1 2018-05-01, 17:01
journal contribution
posted on 2024-06-04, 14:21 authored by Sergey PolyakovskiySergey Polyakovskiy, FCR Spieksma, GJ Woeginger
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).

History

Journal

Journal of combinatorial optimization

Volume

26

Pagination

1-9

Location

New York, N.Y.

Open access

  • Yes

ISSN

1382-6905

eISSN

1573-2886

Language

eng

Publication classification

C Journal article, C1.1 Refereed article in a scholarly journal

Copyright notice

2011, The Authors

Issue

1

Publisher

Springer