Towards a Discipline of Experimental Algorithmics

The last 30 years have seen enormous progress in the design of algorithms, but comparatively little of it has been put into practice, even within academic laboratories. Indeed, the gap between theory and practice has continuously widened over these years. Moreover, many of the recently developed algorithms are very hard to characterize theoretically and, as initially described, suffer from large running-time coefficients. Thus the algorithms and data structures community needs to return to implementation as one of its principal standards of value; we call such an approach Experimental Algorithmics. Experimental Algorithmics studies algorithms and data structures by joining experimental studies with the traditional theoretical analyses. Experimentation with algorithms and data structures is proving indispensable in the assessment of heuristics for hard problems, in the characterization of asymptotic behavior of complex algorithms, in the comparison of competing designs for tractable problems, in the formulation of new conjectures, and in the evaluation of optimization criteria in a multitude of applications. Experimentation is also the key to the transfer of research results from paper to production code, providing as it does a base of well-tested implementations. We present our views on what is a suitable problem to investigate with this approach, what is a suitable experimental setup, what lessons can be learned from the empirical sciences, and what pitfalls await the experimentalist who fails to heed these lessons. We illustrate our points with examples drawn from our research on solutions for NP-hard problems and on comparisons of algorithms for tractable problems, as well as from our experience as reviewer and editor