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}.

Our article on algorithm selection in Wikipedia.

Literature

Tools