  We consider multi-dimensional assignment problems in a probabilistic setting.
Our main results are: (i) A new efficient algorithm for the 3-dimensional
planar problem, based on enumerating and selecting from a set of
"alternating-path trees"; (ii) A new efficient matching-based algorithm for the
3-dimensional axial problem.
