Algorithm selection

Algorithm Selection is technique from meta-algorithmic to select a well-performing algorithm for a given problem instance at hand. It can be seen a special case of a multi-class classification problem where each sample has a weight and getting features can be associated with a cost.

Definition

Given a portfolio ${\mathcal {P}}$ of algorithms ${\mathcal {A}}\in {\mathcal {P}}$, an set of instances $i\in {\mathcal {I}}$ and a cost metric $m:{\mathcal {P}}\times {\mathcal {I}}\to \mathbb {R}$, the algorithm selection problem consists of finding a mapping $s:{\mathcal {I}}\to {\mathcal {P}}$ from instances ${\mathcal {I}}$ to algorithms ${\mathcal {P}}$ such that the cost $\sum _{i\in {\mathcal {I}}}m(s(i),i)$ across all instances is minimized.