Note on generalization in experimental algorithmics

Citation
N. Ramakrishnan et Re. Valdes-perez, Note on generalization in experimental algorithmics, ACM T MATH, 26(4), 2000, pp. 568-580
Citations number
16
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Computer Science & Engineering
Journal title
ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE
ISSN journal
0098-3500 → ACNP
Volume
26
Issue
4
Year of publication
2000
Pages
568 - 580
Database
ISI
SICI code
0098-3500(200012)26:4<568:NOGIEA>2.0.ZU;2-C
Abstract
A recurring theme in mathematical software evaluation is the generalization of rankings of algorithms on test problems to build knowledge-based recomm ender systems for algorithm selection. A key issue is to profile algorithms in terms of the qualitative characteristics of benchmark problems. In this methodological note, we adapt a novel all-pairs algorithm for the profilin g task; given performance rankings for m algorithms on n problem instances, each described with p features, identify a (minimal) subset of p that is u seful for assessing the selective superiority of an algorithm over another, for all pairs of m algorithms. We show how techniques presented in the mat hematical software literature are inadequate for such profiling purposes. I n conclusion, we also address various statistical issues underlying the eff ective application of this technique.