| On 2014-04-08 at 14:00:00 (Brussels Time) |
Abstract
In this presentation, I describe a new approach for analysing the scaling of empirical run-time data of an algorithm when applied to sets of inputs of growing size. My method is based on the use of standard numerical techniques for fitting models, which are then challenged by extrapolation to larger problem sizes and statistically validated using bootstrap confidence intervals. It permits not only the automatic construction of predictive models of the given algorithm’s run-time, but also the comparative evaluation of multiple hypothesis on the scaling in the form of different parametric functions. I will illustrate the method using run-time data for Concorde, a state-of-the-art complete algorithm for the travelling salesperson problem (TSP), applied to a class of well-known Euclidean TSP instances. However, the method is generally applicable to most situations where functional (or statistical) models of the dependence of a performance measure of an algorithm on a single, numerical feature of sets of inpu ts have to be fitted and assessed. I will also present very recent results showing that the additional time required by Concorde for proving optimality after an optimal solution to a given Euclidean TSP instance has been found is surprisingly modest.
