Greedy Matching on the Line
ALAN M. FRIEZE, Colin McDiarmid, Bruce A. Reed · SIAM Journal on Computing · 1990
The problem of finding a perfect matching of small total length in a complete graph whose vertices are points in the interval [0,1] is considered. The greedy heuristic for this problem repeatedly picks the two closest unmatched points x and y, and adds the edge $xy$ to the matching. It is shown that if $2n$ points are randomly chosen uniformly in $[0,1]$, then the expected length of the matching given by the greedy algorithm is $\theta (\log n)$. This compares unfavourably with the length of the shortest perfect matching, which is always less than 1.