Hutter et al. survey ML methods for algorithm runtime prediction

A 2012 paper from Frank Hutter, Lin Xu, Holger H. Hoos, and Kevin Leyton-Brown, posted on arXiv and revised in October 2013, opens with what its authors frame as a perhaps surprising claim: you can predict how long an algorithm will take to run on a previously unseen input, using machine learning to build a model of runtime as a function of problem-specific instance features.

The framing matters because runtime is normally something you measure by actually running the thing. The authors instead treat runtime as a regression target, and argue that such models have important applications to algorithm analysis, portfolio-based algorithm selection, and the automatic configuration of parameterized algorithms. The empirical work covers 11 algorithms and 35 instance distributions across satisfiability, traveling salesperson, and mixed integer programming problems.

The paper's own pitch for what is new, according to the arXiv abstract, is a much more thorough treatment of algorithm parameters as model inputs, alongside extensions of existing models and new families of models. On that basis the authors report substantially better runtime predictions than previous approaches, both on unseen problem instances and on new algorithms drawn from a parameterized space.

The honest caveat is that a survey and evaluation paper is a snapshot of its moment. This one sits in the pre-deep-learning era of empirical algorithmics, and the retrieved abstract does not tell you how the specific feature sets or model families would fare against modern neural approaches, or on workloads outside the SAT, TSP, and MIP triad it evaluates. What it does give you is the framing that has since underpinned a lot of algorithm-selection tooling: treat runtime as a learnable object, and give the model the algorithm's parameters as first-class inputs rather than fixed context.