= Algorithm portfolio
An <algorithm portfolio> combines several candidate <algorithms> or algorithm runs to exploit differences in their performance. It includes a policy for choosing or allocating work, rather than merely naming a collection. A <parallel algorithm portfolio> runs candidates concurrently; a <sequential algorithm portfolio> allocates time on one processor. The original 2001 study compared these approaches and restart strategies on specified distributions of search problems.<Algorithm portfolios by Carla P. Gomes and Bart Selman>[Abstract and sections 4–5, portfolio policies and empirical comparisons]{ref}
Consider invented runtimes $A=(1,30)$ seconds and $B=(30,1)$ seconds on two equally likely instance types. Either algorithm alone has mean $15.5$ seconds. Perfect per-instance <algorithm selection> would take one second before selection overhead. Running both on independent full-speed processors and stopping at the first answer also takes one second under this model, but uses two processors.
For a different policy, run $A$ for at most five seconds, then start $B$ if needed. The two completion times become $1$ and $5+1=6$ seconds, giving mean $3.5$ seconds. This invented <sequential algorithm portfolio> saves time relative to either fixed choice, without matching the two-processor wall time.
Complementary runtimes make these examples work. If all candidates are slow on the same instances, diversity in names supplies no such benefit. Compare wall time, total computing work and overhead separately, and test the allocation policy on new instances. The best completed run chosen retrospectively is a comparison bound, not automatically an implementable selector.
Back to article page
