ALGORITHM: Nearest-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
30631134
31.12
32.13
0.18
0.07
--
E1k.1
30165224
31.23
32.07
0.18
0.07
--
E1k.2
30017206
30.38
31.32
0.19
0.08
--
E1k.3
30040597
29.80
30.60
0.18
0.07
--
E1k.4
30036440
32.33
33.24
0.18
0.07
--
E1k.5
30166887
30.07
30.83
0.17
0.07
--
E1k.6
30469718
30.49
31.52
0.18
0.07
--
E1k.7
30024599
31.23
32.46
0.17
0.07
--
E1k.8
29900530
29.86
31.17
0.18
0.07
--
E1k.9
30349831
29.94
30.73
0.18
0.07
--
E3k.0
53015984
30.47
31.40
0.62
0.28
--
E3k.1
52388108
29.95
30.82
0.64
0.29
--
E3k.2
53071862
31.68
32.66
0.63
0.28
--
E3k.3
53194171
31.05
31.93
0.65
0.29
--
E3k.4
53553035
31.40
32.35
0.61
0.28
--
E10k.0
94551154
?
32.49
2.05
0.89
--
E10k.1
94610310
?
32.20
2.11
0.91
--
E10k.2
94024984
?
31.78
2.08
0.90
--
E31k.0
167782156
?
32.66
7.65
2.48
--
E31k.1
168154412
?
32.77
7.86
2.55
--
E100k.0
297361761
?
32.56
29.19
6.57
--
E100k.1
297136944
?
32.51
29.50
6.64
--
E316k.0
528502832
?
32.60
110.39
15.98
--
E1M.0
939445912
?
32.56
425.72
78.05
--
E3M.0
1670379410
?
32.57
1586.82
309.85
--
E10M.0
2969669610
?
32.57
5681.44
1238.74
--
C1k.0
14551183
27.78
28.48
0.29
0.12
--
C1k.1
14514348
27.58
28.10
0.34
0.14
--
C1k.2
13561463
24.93
25.46
0.31
0.13
--
C1k.3
15250368
28.30
28.98
0.32
0.13
--
C1k.4
15016307
30.58
31.33
0.41
0.17
--
C1k.5
14645262
28.52
29.28
0.33
0.14
--
C1k.6
13008773
27.95
28.89
0.28
0.12
--
C1k.7
13744369
28.88
29.63
0.40
0.17
--
C1k.8
14884490
28.25
28.69
0.35
0.14
--
C1k.9
13959651
27.99
28.83
0.28
0.12
--
C3k.0
25059026
30.53
31.33
1.39
0.63
--
C3k.1
24817926
30.50
31.30
1.63
0.74
--
C3k.2
26040968
33.22
34.16
1.42
0.64
--
C3k.3
24958138
30.61
31.35
1.63
0.74
--
C3k.4
24604009
30.43
31.17
1.59
0.72
--
C10k.0
43559534
?
32.88
8.58
3.71
--
C10k.1
43427794
?
31.76
6.81
2.94
--
C10k.2
43500182
?
32.11
5.94
2.57
--
C31k.0
78481654
?
32.64
21.57
6.99
--
C31k.1
78280165
?
33.04
21.67
7.02
--
C100k.0
138170374
?
32.96
90.17
20.29
--
C100k.1
139006200
?
32.81
92.78
20.88
--
C316k.0
246621470
?
32.89
317.44
45.95
--
M1k.0
--
--
--
--
--
--
M1k.1
--
--
--
--
--
--
M1k.2
--
--
--
--
--
--
M1k.3
--
--
--
--
--
--
M3k.0
--
--
--
--
--
--
M3k.1
--
--
--
--
--
--
M10k.0
--
--
--
--
--
--
dsj1000
24122195
29.27
30.06
0.28
0.12
--
pr1002
321703
24.19
25.29
0.19
0.08
--
si1032
--
--
--
--
--
--
u1060
--
--
--
--
--
--
vm1084
--
--
--
--
--
--
pcb1173
77403
36.05
37.36
0.22
0.09
--
d1291
--
--
--
--
--
--
rl1304
356467
40.93
43.11
0.29
0.12
--
rl1323
380605
40.86
43.18
0.31
0.13
--
nrw1379
72728
28.41
28.96
0.25
0.11
--
fl1400
--
--
--
--
--
--
u1432
196956
28.75
29.12
0.29
0.12
--
fl1577
--
--
--
--
--
--
d1655
--
--
--
--
--
--
vm1748
--
--
--
--
--
--
u1817
--
--
--
--
--
--
rl1889
436093
37.77
39.91
0.40
0.17
--
d2103
--
--
--
--
--
--
u2152
--
--
--
--
--
--
u2319
301550
28.73
28.75
0.44
0.19
--
pr2392
507107
34.14
35.78
0.49
0.21
--
pcb3038
185579
34.78
35.87
0.66
0.30
--
fl3795
--
--
--
--
--
--
fnl4461
234306
28.34
29.05
0.85
0.38
--
rl5915
841112
48.73
51.05
1.59
0.71
--
rl5934
827971
48.90
50.96
1.68
0.75
--
pla7397
31519823
35.51
36.29
2.02
0.89
--
rl11849
--
--
--
--
--
--
usa13509
--
--
--
--
--
--
brd14051
605430
28.99
29.61
4.18
1.72
--
d15112
2021654
28.52
29.19
3.90
1.59
--
d18512
833262
29.14
29.77
4.56
1.78
--
pla33810
94562077
43.17
43.92
14.58
4.68
--
pla85900
196873585
38.29
38.83
51.03
12.52
--