Early Phase Termination
Early phase termination kills slow tasks at a barrier instead of waiting for them, trading some output fidelity for speed [Rin07]. Covered in ECE459 L14.
Why is this okay?
Build a statistical model of program behaviour and verify that killed tasks don’t introduce unacceptable distortion. Report results with a confidence interval, not a single number.
Mario Kart
If you’re in last place when the second-last racer crosses the line, the race is effectively over. No need to wait for you to finish.
Strategies
Branch-and-bound (TSP). Remember previous outcomes. If partial cost already exceeds the best complete solution, abandon this branch. Or stop once you find a solution under a threshold (500 km, even if optimal is 400 km). Or try 5-10 random options and pick the best. No guarantee of optimality.
Monte Carlo / raytracing. Some sample points take much longer. Kill stragglers and interpolate missing values from neighbours. In graphics, a pixel that fails to render can be averaged from adjacent ones and nobody notices.
Majority voting / election calls. Stop once the result is locked in, either an outright majority or when remaining votes can’t change the outcome. News channels sometimes call a race even before the margin is mathematically sealed.
Bounded problems (Rubik’s Cube). Any cube state is solvable in at most 20 moves (“God’s Number”). If your solver hasn’t found a solution in 20 moves, cancel this attempt and try a different path. rubiks-cube-solver.com does both: kills slow branches, and falls back to a 24-move solution if no 20-or-fewer solution is found in time (reduced accuracy).