Monge Property for the multidimensional assignment problem

37 Views Asked by At

I am currently looking into multidimensional assignment problems. I know that for the "classical" two dimensional case i.e. matching two types of objects s.t. a cost function is minimized ("marriage problem") the relaxed problem and the integer problem coincide. By that, I mean that the vertices of the feasible region are all integer. I also know that this is not the case in any dimension $\geq3$.

Now my question is in which cases does the relaxed, multidimensional (i.e. more than two dimensions) assignment problem always have a integer solution. Or even stronger, in which cases are all vertices integer? I'm suspecting that might be answered by the Monge property but I'd be grateful for clarifications, hints in other directions and also suggestions for literature.