ALGORITHM: Nearest-Insertion - 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
29260381
25.26
26.21
0.36
0.15
--
E1k.1
28180189
22.60
23.38
0.35
0.14
--
E1k.2
28831529
25.23
26.13
0.36
0.15
--
E1k.3
29185342
26.10
26.88
0.36
0.15
--
E1k.4
28780449
26.79
27.67
0.35
0.14
--
E1k.5
28595417
23.30
24.02
0.33
0.14
--
E1k.6
29446724
26.11
27.11
0.35
0.14
--
E1k.7
28605098
25.03
26.20
0.34
0.14
--
E1k.8
28802019
25.09
26.35
0.34
0.14
--
E1k.9
28932615
23.88
24.63
0.35
0.14
--
E3k.0
51004142
25.52
26.41
1.18
0.53
--
E3k.1
50437885
25.11
25.95
1.20
0.54
--
E3k.2
50844753
26.16
27.09
1.20
0.54
--
E3k.3
51018177
25.69
26.54
1.20
0.54
--
E3k.4
51227708
25.69
26.60
1.16
0.52
--
E10k.0
90458758
?
26.76
4.02
1.74
--
E10k.1
90502051
?
26.46
4.07
1.76
--
E10k.2
90097834
?
26.27
4.04
1.75
--
E31k.0
160608398
?
26.99
14.19
4.60
--
E31k.1
160538153
?
26.76
14.43
4.67
--
E100k.0
284970234
?
27.03
54.29
12.22
--
E100k.1
285011284
?
27.10
54.93
12.36
--
E316k.0
506499931
?
27.08
200.49
29.02
--
E1M.0
900019649
?
27.00
712.50
130.62
--
E3M.0
1601137780
?
27.07
2531.95
494.40
--
E10M.0
2845652080
?
27.04
9169.73
1999.30
--
C1k.0
14029135
23.20
23.87
0.49
0.20
--
C1k.1
13947570
22.60
23.09
0.53
0.22
--
C1k.2
13187075
21.48
22.00
0.52
0.22
--
C1k.3
14853164
24.96
25.62
0.53
0.22
--
C1k.4
14418904
25.38
26.11
0.64
0.26
--
C1k.5
14034498
23.16
23.88
0.53
0.22
--
C1k.6
12358889
21.56
22.45
0.47
0.19
--
C1k.7
13313681
24.84
25.57
0.59
0.24
--
C1k.8
14275876
23.01
23.43
0.55
0.23
--
C1k.9
13326775
22.19
22.99
0.47
0.19
--
C3k.0
24105319
25.56
26.34
2.07
0.93
--
C3k.1
23634385
24.28
25.04
2.32
1.05
--
C3k.2
24796859
26.85
27.75
2.11
0.95
--
C3k.3
23749955
24.29
24.99
2.30
1.04
--
C3k.4
23687810
25.57
26.28
2.23
1.01
--
C10k.0
41750485
?
27.36
10.81
4.67
--
C10k.1
41810031
?
26.85
8.97
3.88
--
C10k.2
41590690
?
26.31
8.08
3.49
--
C31k.0
75297532
?
27.26
28.60
9.26
--
C31k.1
75282970
?
27.95
28.61
9.27
--
C100k.0
132822997
?
27.82
117.37
26.41
--
C100k.1
133672160
?
27.72
120.30
27.07
--
C316k.0
237139286
?
27.79
418.31
60.54
--
M1k.0
--
--
--
--
--
--
M1k.1
--
--
--
--
--
--
M1k.2
--
--
--
--
--
--
M1k.3
--
--
--
--
--
--
M3k.0
--
--
--
--
--
--
M3k.1
--
--
--
--
--
--
M10k.0
--
--
--
--
--
--
dsj1000
22723010
21.77
22.52
0.46
0.19
--
pr1002
309890
19.63
20.69
0.37
0.15
--
si1032
--
--
--
--
--
--
u1060
--
--
--
--
--
--
vm1084
--
--
--
--
--
--
pcb1173
71105
24.98
26.18
0.47
0.20
--
d1291
--
--
--
--
--
--
rl1304
324817
28.41
30.40
0.58
0.24
--
rl1323
356205
31.83
34.01
0.58
0.24
--
nrw1379
69044
21.90
22.43
0.50
0.21
--
fl1400
--
--
--
--
--
--
u1432
179692
17.47
17.80
0.58
0.24
--
fl1577
--
--
--
--
--
--
d1655
--
--
--
--
--
--
vm1748
--
--
--
--
--
--
u1817
--
--
--
--
--
--
rl1889
398929
26.03
27.98
0.83
0.36
--
d2103
--
--
--
--
--
--
u2152
--
--
--
--
--
--
u2319
265950
13.53
13.55
0.94
0.41
--
pr2392
471443
24.71
26.23
0.95
0.42
--
pcb3038
169742
23.27
24.27
1.26
0.57
--
fl3795
--
--
--
--
--
--
fnl4461
222312
21.77
22.44
1.70
0.76
--
rl5915
730860
29.23
31.25
3.53
1.57
--
rl5934
712545
28.15
29.91
3.63
1.61
--
pla7397
28439674
22.26
22.97
3.66
1.61
--
rl11849
--
--
--
--
--
--
usa13509
--
--
--
--
--
--
brd14051
574893
22.48
23.07
6.97
2.87
--
d15112
1923943
22.30
22.95
6.97
2.84
--
d18512
789750
22.40
22.99
8.25
3.22
--
pla33810
80997007
22.63
23.27
23.65
7.59
--
pla85900
176063269
23.67
24.16
78.54
19.27
--