The three-dimensional matching problem in Kalmanson matrices

S. Polyakovskiy; F.C.R. Spieksma; G.J. Woeginger

doi:10.1007/s10878-011-9426-y

The three-dimensional matching problem in Kalmanson matrices

S. Polyakovskiy, F.C.R. Spieksma, G.J. Woeginger

Onderzoeksoutput: Bijdrage aan tijdschrift › Tijdschriftartikel › Academic › peer review

7 Citaten (Scopus)

1 Downloads (Pure)

Samenvatting

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

Originele taal-2	Engels
Pagina's (van-tot)	1-9
Tijdschrift	Journal of Combinatorial Optimization
Volume	26
Nummer van het tijdschrift	1
DOI's	https://doi.org/10.1007/s10878-011-9426-y
Status	Gepubliceerd - 2013

Toegang tot document

10.1007/s10878-011-9426-y

Citeer dit

@article{d34d60944b014a06ac7c6d2c063e0f1c,

title = "The three-dimensional matching problem in Kalmanson matrices",

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).",

author = "S. Polyakovskiy and F.C.R. Spieksma and G.J. Woeginger",

year = "2013",

doi = "10.1007/s10878-011-9426-y",

language = "English",

volume = "26",

pages = "1--9",

journal = "Journal of Combinatorial Optimization",

issn = "1382-6905",

publisher = "Springer",

number = "1",

}

TY - JOUR

T1 - The three-dimensional matching problem in Kalmanson matrices

AU - Polyakovskiy, S.

AU - Spieksma, F.C.R.

AU - Woeginger, G.J.

PY - 2013

Y1 - 2013

N2 - 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).

AB - 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).

U2 - 10.1007/s10878-011-9426-y

DO - 10.1007/s10878-011-9426-y

M3 - Article

SN - 1382-6905

VL - 26

SP - 1

EP - 9

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

IS - 1

ER -

The three-dimensional matching problem in Kalmanson matrices

Samenvatting

Toegang tot document

Vingerafdruk

Citeer dit