= Censored algorithm runtime
A <censored algorithm runtime> is an evaluation that ends without observing the algorithm's actual completion time. A timeout or <adaptive capping> limit can establish that the run had not finished by the cutoff, supplying <right censoring> rather than an exact completed runtime. The ParamILS capping analysis uses such elapsed-time information to bound comparisons without finishing every run.<ParamILS: An Automatic Algorithm Configuration Framework by Frank Hutter and others>[Section 4, runtime bounds and stopped evaluations]{ref}
Write $T$ for completion time and $C$ for a stopping limit. A simple record is
$$
Y=\min(T,C),\qquad \delta=\mathbf1\{T\le C\},
$$
where $\delta=1$ means completion was observed. The event flag is essential: the same stored duration can mean a completed run or only a lower bound on a still-running computation.
For an original example, two completed runs take $2$ and $5$ seconds and a third is stopped unfinished at $10$ seconds. Averaging the stored durations gives $17/3\approx5.67$ seconds, but that is only a lower bound on the mean of the actual completion times. If the third would take $40$ seconds, the true mean is $47/3\approx15.67$ seconds. Discarding it entirely gives $3.5$ seconds and removes the difficult run from the comparison.
Keep exact observations, cutoff information and any timeout penalty separate. A penalized benchmark score may deliberately assign a stated cost to a timeout; that score is not an observation of $T$. Estimating completion-time distributions additionally requires assumptions about how stopping limits were chosen, particularly when the limits depend on earlier performance.
Back to article page
