Experimental analysis of approximation algorithms for the vertex cover and set covering problems

Experimental analysis of approximation algorithms for the vertex cover and set covering problems

0.00 Avg rating0 Votes
Article ID: iaor20072517
Country: United Kingdom
Volume: 33
Issue: 12
Start Page Number: 3520
End Page Number: 3534
Publication Date: Dec 2006
Journal: Computers and Operations Research
Authors: , , ,
Keywords: heuristics, sets
Abstract:

Several approximation algorithms with proven performance guarantees have been proposed to find approximate solutions to classical combinatorial optimization problems. However, theoretical results may not reflect the experimental performance of the proposed algorithms. As a consequence, a question arises: how ‘far’ from the theoretically proved performance are the experimental results? We conduct a controlled empirical study of approximation algorithms for the Vertex Cover and the Set Covering Problems. Many authors have proposed approximation algorithms for those problems. Our main goal is to better understand their strengths, weaknesses, and operation. Although we implement more than one algorithm to find feasible solutions to either problems, this work does not emphasize competition between them. The quality of the solutions related to the theoretical performance guarantees are analyzed instead. The computational experiments showed that the proven performance guarantees of all tested algorithms did not forecast well the empirical performance.

Reviews

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