Name
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). |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/s10878-011-9426-y | J. Comb. Optim. |
Keywords | DocType | Volume |
Computational complexity,Combinatorial optimization,Tractable case | Journal | 26 |
Issue | ISSN | Citations |
1 | 1382-6905 | 7 |
PageRank | References | Authors |
0.49 | 4 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| S. Polyakovskiy | 1 | 89 | 8.09 |
| Frits C. R. Spieksma | 2 | 591 | 58.84 |
| Gerhard Woeginger | 3 | 4176 | 384.37 |