Rolf Clauberg
IBM J. Res. Dev
We consider a 2-approximation algorithm for Euclidean minimum-cost perfect matching instances proposed by the authors in a previous paper. We present computational results for both random and real-world instances having between 1,000 and 131,072 vertices. The results indicate that our algorithm generates a matching within 2% of optimal in most cases. In over 1,400 experiments, the algorithm was never more than 4% from optimal. For the purposes of the study, we give a new implementation of the algorithm that uses linear space instead of quadratic space, and appears to run faster in practice. © 1996 INFORMS.
Rolf Clauberg
IBM J. Res. Dev
A. Gupta, R. Gross, et al.
SPIE Advances in Semiconductors and Superconductors 1990
Thomas M. Cover
IEEE Trans. Inf. Theory
Michael D. Moffitt
ICCAD 2009