HeldKarp-Based-Christofides Algorithm

Average Percent Excess over the HK Bound and Normalized Running Times

 1000 3162 10K 31K 100K 316K 1M 3.16M 10M
Average Percent Excess over HK Bound
Uniform Points 7.55 7.33 7.30 6.74 6.86 6.85 6.79 -- --
Clustered Points 7.27 7.78 8.37 8.42 8.46 8.56
TSPLIB Instances 7.38 7.12 7.50 6.90 7.42
Random Matrices -- -- --
Average Normalized Running Time in Seconds
Uniform Points 1.0 4.0 14.7 51.4 247.2 971.5 3059.9 -- --
Clustered Points 0.9 3.3 11.6 40.9 197.0 715.1
TSPLIB Instances 0.7 2.2 9.7 50.1 177.9
Random Matrices -- -- --

TSPLIB entries are averages for the following instances:

N=1000 pr1002, pcb1173, rl1304, nrw1379
N=3162 pr2392, pcb3038, fnl4461
N=10k pla7397, brd14051
N=31k pla33810
N=100k pla85900

Note: This may not be a typical sample, since we had to pick instances that most codes
could handle, thus ruling out the many TSPLIB instances with fractional coordinates.