Bounds for the sample size in performance
testing of combinatorial algorithms
by Vesa P. Vaskelainen and Vesa Riihimaki.
The performance of combinatorial algorithms is often evaluated by using
the computational times of a certain number of inputs. The run times of algorithms
with certain type of data appear in computational results as the mean of a small sample.
Still the choice of sample size is rarely based on the distribution of run times.
In this work we use statistical tests to compare the performance of combinatorial
algorithms. Furthermore, we determine confidence intervals for the run times of
combinatorial algorithms. As a consequence, we get easy-to-use bounds of sample size
for justifying the accuracy of computational results.
Confidence interval, combinatorial algorithms, CPU performance,
normal approximation, normality, statistical tests, skewness
Vesa P. Vaskelainen, firstname.lastname@example.org
Vesa Riihimaki, email@example.com
David D. Hanagal, firstname.lastname@example.org
READING THE ARTICLE: You can read the article in
portable document (.pdf) format (165176 bytes.)
NOTE: The content of this article is the intellectual property of the authors, who retains all rights to future publication.
This page has been accessed 2513 times since JULY 28, 2009.
Return to the Home Page.