Average-case performance of three-dimensional assignment heuristics

7 June 2011
Gregory Sorkin
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.
  • Combinatorial Theory Seminar