Produção Nacional
Revisado por pares
Experimental Analysis of Approximation Algorithms for the Vertex Cover and Set Covering Problems
2006; Elsevier BV; Volume: 33; Issue: 12 Linguagem: Inglês
10.1016/j.cor.2005.03.030
ISSN1873-765X
AutoresFernando C. Gomes, Cláudio N. Meneses, Pãnos M. Pardalos, Gerardo Valdísio Rodrigues Viana,
Tópico(s)Computational Geometry and Mesh Generation
ResumoSeveral 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.
Referência(s)