... I would, however, replace the phrase "empirical verification" by "experimental analysis". "Empirical" to me connotes the real-world, whereas we, I presume, wish to consider studies of both real-world and randomly generated instances. In many cases the latter are all we have. "Analysis" is better that "verification" because there are many issues where theory is silent but experiments can yield additional information. Experiments should not only tell us THAT an algorithm runs quickly (or slowly) in practice, but also help us to understand WHY. Also, studies of tuning should when possible be backed up with experiments showing why the tuning works. The best experiments (from a theorists point of view) are the ones that suggest conjectures that one might eventually be able to prove...
(email from D. S. Johnson)

Note: additional info is available at 5th DIMACS Challenge Workshop: Experimental Methodology Day , in particular David Johnson: "A theoretician's guide to the experimental analysis of algorithms" (postscript) .

Back to ALEX98 home page.