Kaoutar El Maghraoui, Gokul Kandiraju, et al.
WOSP/SIPEW 2010
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.
Kaoutar El Maghraoui, Gokul Kandiraju, et al.
WOSP/SIPEW 2010
N.K. Ratha, A.K. Jain, et al.
Workshop CAMP 2000
Lerong Cheng, Jinjun Xiong, et al.
ASP-DAC 2008
S.M. Sadjadi, S. Chen, et al.
TAPIA 2009