 Algorithm portfolio switching overhead

Algorithm portfolio switching overhead is elapsed time or computing work spent changing the active member of an algorithm portfolio, beyond the useful work counted for the candidate algorithms. It can include a context switch, saving or restoring search state, rebuilding data structures and warming a processor's working data. The measured cost depends on the implementation and on what its runtime accounting already includes.

For an explicit model, give one candidate $q$ seconds of useful work, then spend $h$ seconds switching. Repeating equal intervals indefinitely gives useful-time fractionFor $q=1\mathrm{s}$ and $h=0.1\mathrm{s}$, this is $10/11\approx 90.9\%$. Reducing the useful interval to $0.1\mathrm{s}$ with the same switch cost drops the fraction to $1/2$. Small time slices improve responsiveness but can consume more of the budget in switching.

Terminal bookkeeping matters. In the illustrative algorithm portfolio schedule where A and B alternate one-second useful intervals, A completes after its third interval and B has received two. Four switches occur before completion. With $0.1\mathrm{s}$ per switch, elapsed time is $5+4(0.1)=5.4\mathrm{s}$; there is no fifth switch after the stopping rule has fired. Comparing this with the zero-overhead $5\mathrm{s}$ trace isolates the stipulated switching cost.

The original portfolio experiments distinguish interleaving from parallel and restart execution.^[ref] Applying such policies requires distinguishing switching cost from algorithmic work that is abandoned. If a run is discarded and restarted, lost progress changes the completion process itself; treating it as a fixed additive switch cost can misrepresent the sequential algorithm portfolio. Report whether timings include initialization, state transfer and result checking, and measure the actual switching events.