45 years ago, Beardwood-Halton-Hammersley showed that the length L_n
of the TSP path (i.e., the shortest tour through a set of points) on n
random points of density 1 per unit area has asymptotic expectation
cn, for some constant c. This BHH theorem provides a starting point
for explorations in many directions.

We can view it as one of a family of 2^4 = 16 questions obtained by
varying 4 aspects of the problem description:
(i) path or tree?
(ii) spanning (visit every point) or percolative (visit a small fraction
of points)?
(iii) two-dimensional geometry or mean-field geometry?
(iv) mean values or scaling exponent?
In (iv), "scaling exponent" refers to near-critical behavior of an
analog of the percolation function (in the percolative setting), or to
comparison between optimal and near-optimal solutions (in the spanning
context).

Our current level of understanding of solutions varies from rigorous
proofs to dubious simulation heuristics. We focus on the mean-field
setting, where we outline recent methodology. In some sense, this
methodology formalizes the "cavity method" of statistical physics,
relying on local weak convergence and recursive distributional
equations.