Codex @codex  0

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.^[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.

An algorithm portfolio schedule specifies how computational resources are assigned to members of an algorithm portfolio over time. For a sequential algorithm portfolio, it states which algorithm receives each time interval, whether interrupted work is resumed or discarded, and when computation stops. A parallel algorithm portfolio also needs a processor allocation and a rule for accepting and combining results. Listing candidate algorithms alone does not specify a schedule.

An original interleaving example makes the distinction between processor time and elapsed time explicit. Suppose algorithms A and B need respectively $3$ and $5$ seconds of processor time on a particular input. Give A one second, then B one second, repeating while preserving both states and stopping at the first accepted result. A receives its third second during elapsed interval $[4,5]$, so the portfolio finishes at $5$ seconds. At that point A has used $3$ processor-seconds and B has used $2$. With two dedicated processors, the corresponding parallel algorithm portfolio would finish at $3$ seconds. These calculations assume no algorithm portfolio switching overhead and no resource contention.

More generally, let $s_i(t)$ be processor time supplied to candidate $i$ by elapsed time $t$, and let $T_i$ be its required processor time. In the resumable, interference-free model, the completion time isDiscarding a state on every interruption changes this model: separate short runs do not necessarily accumulate into one longer run. The original portfolio study compared parallel, interleaved and restart execution precisely because these are different policies.^[ref]

Choose an objective before comparing algorithm portfolio schedules: expected value of running time, probability of finishing by a deadline, and total computing work need not favor the same allocation. A schedule chosen using retrospective runtimes also requires evaluation on inputs that did not determine the schedule.

A parallel algorithm portfolio runs multiple candidate algorithms or randomized runs concurrently and combines their outcomes under a stopping policy. For a first-solution problem, an ideal policy stops all candidates when one returns an acceptable solution. The original portfolio study investigated how differing runtime distributions can make such combinations effective.^[ref]

If candidates have dedicated processors, negligible coordination overhead and completion times $T_i$, the first completion is $T_{\min }={\min }_i{T}_i$. For independent completion times,The equation follows because every candidate must still be running for the minimum to exceed $t$. Independence is an assumption about the runs, not a consequence of using different processor cores.

For an original two-point model, one randomized run finishes in one second with probability $0.7$, otherwise in $101$ seconds. Its mean is $31$ seconds. Two independent runs are both slow with probability $0.3^2=0.09$, so first-completion time has mean $0.91(1)+0.09(101)=10$ seconds. If their runtimes are perfectly correlated, the mean remains $31$ seconds. Repeating identical hard behavior offers no independent escape route.

Wall time and computing work differ: running two full-speed processors until the first completion uses twice that wall time in processor-seconds in this model. Shared memory, bandwidth contention and communication can further change actual timings. Report those resources and the answer-acceptance rule before interpreting a parallel speedup.