AN ASYMPTOTIC DETERMINATION OF THE MINIMUM SPANNING TREE AND MINIMUM MATCHING CONSTANTS IN GEOMETRICAL-PROBABILITY

Given n uniformly and independently distributed points in a ball of unit volume in dimension d, it is well established that the length of several combinatorial optimization problems (including the minimum spanning tree (MST), the minimum matching (M), the travelling salesman problem (TSP), etc.) on these n points is asymptotic to β(d)n(d-1)/d, where the constant β(d) for these problems. In this paper progress is made in establishing the constants βMST(d), βM(d) for the MST and the matching problem. By applying Crofton's method, an old method in geometrical probability, it is proved that βMST(d)∼√d/(2πe, βM(d)∼ 1 2√d/(2πe) as d tends to infinity. Moreover, the method presented here corresponds to heuristics for these problems, which are asymptotically exact as the dimension increases. Finally, the asymptotics for the TSP constant are examined. © 1990.