What to measure
Catherine C. McGeoch · 2006
One of the rst questions the algorithmic experimenter faces is: What should I measure? This talk will focus on measuring solution quality, and will survey a variety of performance indicators that can be considered when undertaking computational research on algorithms. Some performance indicators such as the number of colors used, the length of the tour, or the number of problem instances solved to optimality are immediately suggested by the context of the algorithmic problem. However, alternative performance indicators may produce better experimental results. I will draw on a variety of nontraditional statistical methodologies, including graphical analysis, exploratory data analysis, variance reduction techniques, and use of biased estimators, to show how alternative performance indicators can lead to more e cient and powerful experiments, clearer analyses, and stronger conclusions about algorithm performance.