Cost-Effectiveness of Algorithms

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 of 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 cost-effective approximation to K(x) then τ(n) = O(n2).