When trying to solve a computational problem we are often faced with a choice among algorithms that are all guaranteed to return the right answer but that differ in their runtime distributions (e.g., SAT solvers, sorting algorithms). This paper aims to lay theoretical foundations for such choices by formalizing preferences over runtime distributions. It might seem that we should simply prefer the algorithm that minimizes expected runtime. However, such preferences would be driven by exactly how slow our algorithm is on bad inputs, whereas in practice we are typically willing to cut off occasional, sufficiently long runs before they finish. We propose a principled alternative, taking a utility-theoretic approach to characterize the scoring functions that describe preferences over algorithms. These functions depend on the way our value for solving our problem decreases with time and on the distribution from which captimes are drawn. We describe examples of realistic utility functions and show how to leverage a maximum-entropy approach for modeling underspecified captime distributions. Finally, we show how to efficiently estimate an algorithm's expected utility from runtime samples.

该论文旨在通过形式化运行时分布的喜好来解决在算法选择中的竞争。我们提出了一种基于效用理论的方法，描述了算法偏好的评分函数，这些函数依赖于解决问题的价值如何随时间降低以及满足的时间分布。我们展示了实用程序函数的例子，并展示了如何利用最大熵方法来建模未规定的时间分布，最后，我们展示了如何从运行时样本中高效估计算法的预期效用。

正式化运行时分布的偏好