Figure 1
Average wall-clock runtime, T̄t
Cumulative mean, in milliseconds, of the per-trial wall-clock time spent by each heuristic, plotted against the trial index t.
Fig. 1. Running mean of Tt(A) = wall-clock time of algorithm A on trial t, averaged over t₁…t.
Figure 2
Empirical approximation ratio, ᾱt
Cumulative mean of α(A,I) = ℓ(A(I)) / OPT(I), with OPT obtained exactly by Held–Karp. The dashed rule marks the optimal regime α = 1.
Fig. 2. Running mean of α(A, It) with It ∼ U(random Euclidean instances of size n).