Cost-effectiveness of algorithms

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).
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2015, Vol. 17 no. 1 (in progress) (1), pp.201--218
Liste complète des métadonnées

Littérature citée [26 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01196858
Contributeur : Coordination Episciences Iam <>
Soumis le : jeudi 10 septembre 2015 - 15:17:20
Dernière modification le : mardi 24 octobre 2017 - 11:24:02
Document(s) archivé(s) le : mardi 29 décembre 2015 - 00:02:06

Fichier

dmtcs-17-1-14.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01196858, version 1

Collections

Citation

Graham Farr. Cost-effectiveness of algorithms. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2015, Vol. 17 no. 1 (in progress) (1), pp.201--218. 〈hal-01196858〉

Partager

Métriques

Consultations de la notice

119

Téléchargements de fichiers

376