Algorithms in a Nutshell

Empirical Evaluation Format

The implementations of the algorithms are all executed with a series of benchmark problems, appropriate for each individual algorithm. The appendix provides more detail on the mechanisms used for timing purposes. In general, we execute all algorithms on two different platforms: a common desktop environment and a high-end Linux cluster. Together these provide a range within which most systems should exist. To properly evaluate the performance, a test suite is composed of a set of k individual trials (typically k≥10). The best and worst performers are discarded as outliers, the remaining k−2 trials are aggregated, and the average and standard deviations are computed. Tables are shown with problem size instances ranging from n=2 to 2²⁰.