Algorithm Selection

Given a set $\mathcal{I}$ of problem instances and a distribution $\mathcal{D}$ over $\mathcal{I}$ , a space of algorithms $\mathcal{A}$ , and a performance measure $m: \mathcal{I} \times \mathcal{A} \rightarrow \mathbb{R}$ , the per-instance algorithm selection problem is to find a mapping $s: \mathcal{I} \rightarrow \mathcal{A}$ that optimizes $\mathbb{E}_{i \sim \mathcal{D}}m(i, s(i))$ , the performance measure achieved by running the selected algorithm $s(i)$ for instance $i$ , in expectation across instances $i \in \mathcal{I}$ drawn from distribution $\mathcal{D}$ .