Computational experience with an approximation algorithm on large-scale Euclidean matching instances

Computational experience with an approximation algorithm on large-scale Euclidean matching instances

0.00 Avg rating0 Votes
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: ,
Keywords: computational analysis
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.