Cost-effectiveness of algorithms
Graham Farr
Abstract
In this paper we discuss how to assess the performance of algorithms
for optimisation problems in a way that balances solution quality and
time. We propose measures of cost-effectiveness for such
algorithms. These measures give the gain in solution quality per time
unit over a sequence of inputs, and give a basis for deciding which
algorithm to use when aiming for best accumulated solution quality for
a given time investment over such an input
sequence. Cost-effectiveness measures can be defined for both
average-case and worst-case performance. We apply these ideas to three
problems: maximum matching, graph colouring and Kolmogorov
complexity. For the latter, we propose a cost-effectiveness measure
for the time-bounded complexity Kτ(x), and
argue that it can be used to measure the cost-effectiveness both of
finding a short program to output x and of generating
x from such a program. Under mild assumptions, we show
that (roughly speaking) if the time-bounded complexity
Kτ(x) is to be a cost-effective
approximation to K(x) then
τ(n)=O(n2).
Full Text: PDF PostScript