Testing of Heuristic Methods: A Case Study of Greedy Algorithm

Abstract : Algorithms which seek global optima are computationally expensive. Alternatively, heuristic methods have been proposed to find approximate solutions. Because heuristic algorithms do not always deliver exact solutions it is difficult to verify the computed solutions. Such a problem is known as the oracle problem. In this paper, we propose to apply Metamorphic Testing (MT) in such situations because MT is designed to alleviate the oracle problem and can be automated. We demonstrate the failure detection capability of MT on testing a heuristic method, called the Greedy Algorithm (GA), applied to solve the set covering problem (SCP). The experimental results show that MT is an effective method to test GA.
Type de document :
Communication dans un congrès
Zbigniew Huzar; Radek Koci; Bertrand Meyer; Bartosz Walter; Jaroslav Zendulka. 3rd Central and East European Conference on Software Engineering Techniques (CEESET), Oct 2008, Brno, Czech Republic. Springer, Lecture Notes in Computer Science, LNCS-4980, pp.246-260, 2011, Software Engineering Techniques. 〈10.1007/978-3-642-22386-0_19〉
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01572541
Contributeur : Hal Ifip <>
Soumis le : lundi 7 août 2017 - 16:51:16
Dernière modification le : lundi 7 août 2017 - 16:53:37

Fichier

978-3-642-22386-0_19_Chapter.p...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

A. Barus, T. Chen, D. Grant, F. Kuo, M. Lau. Testing of Heuristic Methods: A Case Study of Greedy Algorithm. Zbigniew Huzar; Radek Koci; Bertrand Meyer; Bartosz Walter; Jaroslav Zendulka. 3rd Central and East European Conference on Software Engineering Techniques (CEESET), Oct 2008, Brno, Czech Republic. Springer, Lecture Notes in Computer Science, LNCS-4980, pp.246-260, 2011, Software Engineering Techniques. 〈10.1007/978-3-642-22386-0_19〉. 〈hal-01572541〉

Partager

Métriques

Consultations de la notice

24

Téléchargements de fichiers

10