An asymptotic determination of the minimum spanning tree and minimum matching constants in geometrical probability

An asymptotic determination of the minimum spanning tree and minimum matching constants in geometrical probability

0.00 Avg rating0 Votes
Article ID: iaor1991600
Country: Netherlands
Volume: 9
Issue: 4
Start Page Number: 223
End Page Number: 231
Publication Date: Jul 1990
Journal: Operations Research Letters
Authors: ,
Keywords: minimum spanning trees
Abstract:

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 equ1equ2, where the constant equ3depends on the dimension d and the problem solved. It has been a long open problem to determine the constants equ4for these problems. In this paper progress is made in establishing the constants equ5, equ6for the MST and the matching problem. By applying Crofton's method, an old method in geometrical probability, it is proved thatequ7, equ8as 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.

Reviews

Required fields are marked *. Your email address will not be published.