Karp-Partitioning:Size=20 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 21.17 25.09 29.34 27.52 32.00 36.11 24.17 27.06 --
Clustered Points 56.19 82.15 96.88 84.81 91.41 99.45
TSPLIB Instances 33.06 26.17 64.01 54.86 56.55
Random Matrices -- -- --
Average Normalized Running Time in Seconds
Uniform Points 12.5 2.1 0.8 271.7 28.4 10.1 4098.1 666.5 --
Clustered Points 13.2 2.2 0.9 282.7 29.0 10.0
TSPLIB Instances 51.2 309.8 37.0 1099.0 8.0
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.