The 2-dimensional assignment problem (minimum cost matching) is solvable in polynomial time, and it is known that a random instance of size n, with entries chosen independently and uniformly at random from [0,1], has expected cost tending to π^2/6. In dimensions 3 and higher, the "planar" assignment problem is NP-complete, but what is the expected cost for a random instance, and how well can a heuristic do? In d dimensions, the expected cost is of order at least n^{2-d} and at most ln n times larger, but the upper bound is non-constructive. For 3 dimensions, we show a heuristic capable of producing a solution within a factor n^ε of the lower bound, for any constant ε, in time of order roughly n^{1/ε}. In dimensions 4 and higher, the question is wide open: we don't know any reasonable average-case assignment heuristic.
