Article ID: | iaor19972048 |
Country: | United States |
Volume: | 8 |
Issue: | 1 |
Start Page Number: | 29 |
End Page Number: | 40 |
Publication Date: | Jan 1996 |
Journal: | INFORMS Journal On Computing |
Authors: | Goemans Michel X., Williamson David P. |
Keywords: | computational analysis |
The authors consider a 2-approximation algorithm for Euclidean minimum-cost perfect matching instances proposed by the authors in a previous paper. They present computational results for both random and real-world instances having between 1,000 and 131,072 vertices. The results indicate that the present 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, the authors give a new implementation of the algorithm that uses linear space instead of quadratic space, and appears to run faster in practice.