Publication Details

Hybrid Ranking and Regression for Algorithm Selection

authored by
Jonas Hanselle, Alexander Tornede, Marcel Wever, Eyke Hüllermeier

Algorithm selection (AS) is defined as the task of automatically selecting the most suitable algorithm from a set of candidate algorithms for a specific instance of an algorithmic problem class. While suitability may refer to different criteria, runtime is of specific practical relevance. Leveraging empirical runtime information as training data, the AS problem is commonly tackled by fitting a regression function, which can then be used to estimate the candidate algorithms’ runtimes for new problem instances. In this paper, we develop a new approach to algorithm selection that combines regression with ranking, also known as learning to rank, a problem that has recently been studied in the realm of preference learning. Since only the ranking of the algorithms is eventually needed for the purpose of selection, the precise numerical estimation of runtimes appears to be a dispensable and unnecessarily difficult problem. However, discarding the numerical runtime information completely seems to be a bad idea, as we hide potentially useful information about the algorithms’ performance margins from the learner. Extensive experimental studies confirm the potential of our hybrid approach, showing that it often performs better than pure regression and pure ranking methods.

External Organisation(s)
Paderborn University
Contribution to book/anthology
No. of pages
Publication date
Publication status
Peer reviewed
ASJC Scopus subject areas
Theoretical Computer Science, Computer Science(all)
Electronic version(s) (Access: Closed)