7
$\begingroup$

I recently learned about the multidimensional version of the assignment problem (the 1:1 version was studied in the Kuhn-Murkes Hungarian algorithm for bipartite graphs).

The article I was reading was about 1:1:1 or three-sided matches and above -- and it was claimed that the multidimensional version was NP-hard. What?! I am shocked by this, and I'm not even sure I believe it.

My first question is: Can someone point to the paper containing the proof? I couldn't find this easily.

But the bigger question is: What is the intuition behind why the 2D version can be solved in polynomial time, and the higher dimensions cannot? It seems like there should be some generalization of the Hungarian that works in higher dimensions.

I don't understand the intuition for why this doesn't work, and it seems bizarre.

$\endgroup$
2

1 Answer 1

3
$\begingroup$

As suggested by OP in the comments, I am making my comment an answer.

A proof of the statement can be found in this paper.

Citation: A.M. Frieze. "Complexity of a 3-dimensional assignment problem." European Journal of Operational Research, vol. 13, issue 2, 1983, pp.161-164. doi: 10.1016/0377-2217(83)90078-4.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .