Worst‐case greedy matchings in the unit d‐cube

Publisher Website
Google Scholar
Abstract
The worst‐case behavior of greedy matchings of n points in the unit d‐cube, where d ≥ 2, is analyzed. The weighting function is taken to be the α'th power of Euclidean distance, where 0 < α < d. It is proved that the asymptotic growth rate of the weight of such a greedy matching is exactly βn(d‐α)/d, where β is a positive constant that depends on the parameters α and d. Included in the analysis is a minimax theorem equating the worstcase behaviors of matchings resulting from greedy algorithms that, when ordering edges for the greedy process, break ties in different ways.