 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.^[ref]

Write $T$ for completion time and $C$ for a stopping limit. A simple record iswhere $\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\approx 5.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\approx 15.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.