ALGORITHM: Nearest-Augmented-Addition - Jon Bentley's kd-tree based implementation

MACHINE: Silicon Graphics 196 Mhz MIPS R10000 [ mips196 ]

RUN: 1

SUBMITTER: Johnson-McGeoch

Instance
Tour Length
Percent over OPT
Percent over HK
Running Time (Seconds)
Normalized Time
Memory Usage (Megabytes)
E1k.0
29292827
25.39
26.35
0.24
0.10
--
E1k.1
28182685
22.61
23.39
0.24
0.10
--
E1k.2
28837510
25.25
26.16
0.24
0.10
--
E1k.3
29185342
26.10
26.88
0.24
0.10
--
E1k.4
28780449
26.79
27.67
0.24
0.10
--
E1k.5
28597377
23.30
24.03
0.24
0.10
--
E1k.6
29373567
25.80
26.79
0.24
0.10
--
E1k.7
28605098
25.03
26.20
0.23
0.10
--
E1k.8
28864698
25.36
26.62
0.23
0.10
--
E1k.9
28971703
24.04
24.80
0.24
0.10
--
E3k.0
51006970
25.53
26.42
0.81
0.37
--
E3k.1
50441751
25.12
25.96
0.84
0.38
--
E3k.2
50846803
26.16
27.10
0.83
0.37
--
E3k.3
51037749
25.74
26.59
0.84
0.38
--
E3k.4
51254407
25.76
26.67
0.81
0.37
--
E10k.0
90475496
?
26.78
2.73
1.18
--
E10k.1
90524743
?
26.49
2.71
1.17
--
E10k.2
90102388
?
26.28
2.70
1.17
--
E31k.0
160752708
?
27.10
9.80
3.17
--
E31k.1
160565111
?
26.78
10.02
3.25
--
E100k.0
285130492
?
27.10
38.00
8.55
--
E100k.1
285148964
?
27.16
38.01
8.55
--
E316k.0
506744689
?
27.08
139.94
20.25
--
E1M.0
900501944
?
27.06
520.80
95.48
--
E3M.0
1601968850
?
27.14
1891.96
369.44
--
E10M.0
2847209520
?
27.11
6791.11
1480.68
--
C1k.0
14036890
23.27
23.94
0.37
0.15
--
C1k.1
13947570
22.60
23.09
0.40
0.17
--
C1k.2
13187075
21.48
22.00
0.39
0.16
--
C1k.3
14874529
25.14
25.80
0.39
0.16
--
C1k.4
14461304
25.75
26.48
0.49
0.20
--
C1k.5
14065771
23.44
24.16
0.40
0.17
--
C1k.6
12403698
22.00
22.90
0.35
0.14
--
C1k.7
13313526
24.84
25.56
0.47
0.19
--
C1k.8
14275876
23.01
23.43
0.42
0.17
--
C1k.9
13326775
22.19
22.99
0.36
0.15
--
C3k.0
24159584
25.84
26.62
1.62
0.73
--
C3k.1
23638889
24.30
25.06
1.88
0.85
--
C3k.2
24832516
27.04
27.93
1.69
0.76
--
C3k.3
23790545
24.50
25.21
1.87
0.84
--
C3k.4
23710287
25.69
26.40
1.83
0.83
--
C10k.0
41793852
?
27.49
9.33
4.03
--
C10k.1
41822921
?
26.89
7.54
3.26
--
C10k.2
41662764
?
26.53
6.63
2.87
--
C31k.0
75341435
?
27.33
23.96
7.76
--
C31k.1
75350752
?
28.06
24.10
7.81
--
C100k.0
132902274
?
27.89
100.11
22.52
--
C100k.1
133794624
?
27.83
102.68
23.10
--
C316k.0
237313602
?
27.88
352.54
51.03
--
M1k.0
--
--
--
--
--
--
M1k.1
--
--
--
--
--
--
M1k.2
--
--
--
--
--
--
M1k.3
--
--
--
--
--
--
M3k.0
--
--
--
--
--
--
M3k.1
--
--
--
--
--
--
M10k.0
--
--
--
--
--
--
dsj1000
22825434
22.32
23.07
0.35
0.14
--
pr1002
309890
19.63
20.69
0.25
0.10
--
si1032
--
--
--
--
--
--
u1060
--
--
--
--
--
--
vm1084
--
--
--
--
--
--
pcb1173
74213
30.45
31.70
0.29
0.12
--
d1291
--
--
--
--
--
--
rl1304
337650
33.49
35.55
0.36
0.15
--
rl1323
360964
33.59
35.80
0.37
0.16
--
nrw1379
69117
22.03
22.56
0.34
0.14
--
fl1400
--
--
--
--
--
--
u1432
181631
18.74
19.07
0.38
0.16
--
fl1577
--
--
--
--
--
--
d1655
--
--
--
--
--
--
vm1748
--
--
--
--
--
--
u1817
--
--
--
--
--
--
rl1889
419052
32.39
34.44
0.50
0.21
--
d2103
--
--
--
--
--
--
u2152
--
--
--
--
--
--
u2319
266268
13.67
13.69
0.64
0.28
--
pr2392
471692
24.78
26.29
0.63
0.28
--
pcb3038
172318
25.15
26.16
0.84
0.38
--
fl3795
--
--
--
--
--
--
fnl4461
222457
21.85
22.52
1.15
0.52
--
rl5915
764744
35.23
37.33
1.88
0.83
--
rl5934
745337
34.04
35.89
1.98
0.88
--
pla7397
28774926
23.71
24.42
2.51
1.10
--
rl11849
--
--
--
--
--
--
usa13509
--
--
--
--
--
--
brd14051
575255
22.56
23.15
5.28
2.18
--
d15112
1924030
22.31
22.95
4.93
2.01
--
d18512
790305
22.48
23.08
5.86
2.28
--
pla33810
82929598
25.56
26.21
16.93
5.43
--
pla85900
177667706
24.78
25.29
59.72
14.66
--