Proceedings

Algorithm Runtime Prediction: Methods and Evaluation (Extended Abstract)

Frank Hutter, Lin Xu, Holger H. Hoos, Kevin Leyton-Brown

Download BibTeX Cite

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Journal Track. Pages 4197-4200.

Abstract

Perhaps surprisingly, it is possible to predict how long an algorithm will take to run on a previously unseen input, using machine learning techniques to build a model of the algorithm's runtime as a function of problem-specific instance features. Such models have many important applications and over the past decade, a wide variety of techniques have been studied for building such models. In this extended abstract of our 2014 AI Journal article of the same title, we summarize existing models and describe new model families and various extensions. In a comprehensive empirical analysis using 11 algorithms and 35 instance distributions spanning a wide range of hard combinatorial problems, we demonstrate that our new models yield substantially better runtime predictions than previous approaches in terms of their generalization to new problem instances, to new algorithms from a parameterized space, and to both simultaneously.

Frank Hutter, Lin Xu, Holger H. Hoos, and Kevin Leyton-Brown. 2015. Algorithm Runtime Prediction: Methods and Evaluation (Extended Abstract). In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15. IJCAI, 4197–4200. https://ijcai.org/proceedings/2015/595
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards