# Algorithm Portfolio Design: Theory vs. Practice

arXiv: https://arxiv.org/abs/1302.1541 · HTML: https://mlsanity.com/paper/1302.1541/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Feb 2013.

## Built on by (most cited first, 2 of 2)

- [Evidence for Long-Tails in SLS Algorithms](https://mlsanity.com/paper/2107.00378/) (2021)
- [Towards an Understanding of Long-Tailed Runtimes of SLS Algorithms](https://mlsanity.com/paper/2210.13159/) (2022)

## Abstract (arXiv)

Stochastic algorithms are among the best for solving computationally hard search and reasoning problems. The runtime of such procedures is characterized by a random variable. Different algorithms give rise to different probability distributions. One can take advantage of such differences by combining several algorithms into a portfolio, and running them in parallel or interleaving them on a single processor. We provide a detailed evaluation of the portfolio approach on distributions of hard combinatorial search problems. We show under what conditions the protfolio approach can have a dramatic computational advantage over the best traditional methods.