Rafae Bhatti, Elisa Bertino, et al.
Communications of the ACM
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.
Rafae Bhatti, Elisa Bertino, et al.
Communications of the ACM
Robert G. Farrell, Catalina M. Danis, et al.
RecSys 2012
Eric Price, David P. Woodruff
FOCS 2011
Robert C. Durbeck
IEEE TACON