Premium
Worst‐case greedy matchings in the unit d ‐cube
Author(s) -
Snyder Timothy Law,
Steele J. Michael
Publication year - 1990
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230200607
Subject(s) - combinatorics , greedy algorithm , mathematics , matching (statistics) , unit cube , constant (computer programming) , weighting , polytope , unit (ring theory) , euclidean geometry , minimax , discrete mathematics , mathematical optimization , computer science , statistics , medicine , geometry , radiology , programming language , mathematics education
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.