Yao Qi, Raja Das, et al.
ISSTA 2009
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.
Yao Qi, Raja Das, et al.
ISSTA 2009
Elizabeth A. Sholler, Frederick M. Meyer, et al.
SPIE AeroSense 1997
Robert C. Durbeck
IEEE TACON
Michael D. Moffitt
ICCAD 2009