Chidanand Apté, Fred Damerau, et al.
ACM Transactions on Information Systems (TOIS)
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.
Chidanand Apté, Fred Damerau, et al.
ACM Transactions on Information Systems (TOIS)
N.K. Ratha, A.K. Jain, et al.
Workshop CAMP 2000
Raymond Wu, Jie Lu
ITA Conference 2007
Yao Qi, Raja Das, et al.
ISSTA 2009