Paper Info
Title
A Statistical Approach for Algorithm Selection
Abstract
This paper deals with heuristic algorithm characterization, which is applied to the solution of an NP-hard problem, in order to select the best algorithm for solving a given problem instance. The traditional approach for selecting algorithms compares their performance using an instance set, and concludes that one outperforms the other. Another common approach consists of developing mathematical models to relate performance to problem size. Recent approaches try to incorporate more characteristics. However, they do not identify the characteristics that affect performance in a critical way, and do not incorporate them explicitly in their performance model. In contrast, we propose a systematic procedure to create models that incorporate critical characteristics, aiming at the selection of the best algorithm for solving a given instance. To validate our approach we carried out experiments using an extensive test set. In particular, for the classical bin packing problem, we developed models that incorporate the interrelation among five critical characteristics and the performance of seven heuristic algorithms. As a result of applying our procedure, we obtained a 76% accuracy in the selection of the best algorithm.
Year
DOI
Venue
2004
10.1007/978-3-540-24838-5_31
Lecture Notes in Computer Science
Keywords
Field
DocType
np hard problem,mathematical model,bin packing problem,heuristic algorithm
Heuristic,Mathematical optimization,Heuristic (computer science),Computer science,Performance model,Algorithm Selection,Mathematical model,Bin packing problem,Statistical analysis,Test set
Conference
Volume
ISSN
Citations 
3059
0302-9743
5
PageRank 
References 
Authors
0.51
11
6
Name
Order
Citations
PageRank
Joaquín Pérez1459.56
Rodolfo A. Pazos22910.95
Juan Frausto Solís33912.02
Guillermo Rodríguez4346.46
David Romero5223.65
Laura Cruz68928.40