ALGORITHM: Random-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
31146757
33.33
34.35
0.08
0.03
--
E1k.1
30701731
33.57
34.42
0.07
0.03
--
E1k.2
31169045
35.38
36.36
0.08
0.03
--
E1k.3
30625856
32.33
33.14
0.09
0.04
--
E1k.4
31603058
39.23
40.19
0.07
0.03
--
E1k.5
30837495
32.96
33.74
0.08
0.03
--
E1k.6
33425317
43.15
44.28
0.08
0.03
--
E1k.7
31414617
37.31
38.59
0.07
0.03
--
E1k.8
32056852
39.22
40.63
0.08
0.03
--
E1k.9
30779721
31.78
32.58
0.07
0.03
--
E3k.0
56958929
40.18
41.17
0.27
0.12
--
E3k.1
54837847
36.02
36.94
0.29
0.13
--
E3k.2
55302886
37.22
38.23
0.29
0.13
--
E3k.3
55367807
36.41
37.32
0.27
0.12
--
E3k.4
56307389
38.15
39.16
0.27
0.12
--
E10k.0
99703817
?
39.72
0.88
0.38
--
E10k.1
99378307
?
38.86
0.90
0.39
--
E10k.2
98614481
?
38.21
0.88
0.38
--
E31k.0
178189694
?
40.89
3.34
1.08
--
E31k.1
177305266
?
40.00
3.37
1.09
--
E100k.0
316181310
?
40.94
13.90
3.13
--
E100k.1
313915622
?
39.99
14.08
3.17
--
E316k.0
559811373
?
40.39
52.00
7.53
--
E1M.0
995578168
?
40.48
196.71
36.06
--
E3M.0
1767291350
?
40.26
709.00
138.44
--
E10M.0
3146932520
?
40.49
2503.24
545.79
--
C1k.0
14255989
25.19
25.87
0.07
0.03
--
C1k.1
14551615
27.91
28.42
0.09
0.04
--
C1k.2
14326801
31.98
32.54
0.07
0.03
--
C1k.3
15691753
32.01
32.71
0.07
0.03
--
C1k.4
14635609
27.27
28.00
0.07
0.03
--
C1k.5
15204219
33.43
34.21
0.07
0.03
--
C1k.6
13787558
35.61
36.61
0.07
0.03
--
C1k.7
14159145
32.77
33.54
0.08
0.03
--
C1k.8
15257945
31.47
31.92
0.07
0.03
--
C1k.9
14430191
32.30
33.17
0.07
0.03
--
C3k.0
25981905
35.33
36.17
0.27
0.12
--
C3k.1
26696786
40.38
41.24
0.27
0.12
--
C3k.2
26255357
34.32
35.26
0.27
0.12
--
C3k.3
26620488
39.31
40.10
0.27
0.12
--
C3k.4
26035614
38.02
38.80
0.27
0.12
--
C10k.0
46715051
?
42.50
0.87
0.38
--
C10k.1
46768572
?
41.90
0.87
0.38
--
C10k.2
45422290
?
37.95
0.87
0.38
--
C31k.0
83837489
?
41.69
3.24
1.05
--
C31k.1
82838050
?
40.79
3.29
1.07
--
C100k.0
147539437
?
41.98
13.71
3.08
--
C100k.1
147321786
?
40.76
13.67
3.08
--
C316k.0
262384128
?
41.39
51.07
7.39
--
M1k.0
--
--
--
--
--
--
M1k.1
--
--
--
--
--
--
M1k.2
--
--
--
--
--
--
M1k.3
--
--
--
--
--
--
M3k.0
--
--
--
--
--
--
M3k.1
--
--
--
--
--
--
M10k.0
--
--
--
--
--
--
dsj1000
25073031
34.37
35.19
0.07
0.03
--
pr1002
341704
31.91
33.08
0.08
0.03
--
si1032
--
--
--
--
--
--
u1060
--
--
--
--
--
--
vm1084
--
--
--
--
--
--
pcb1173
78784
38.48
39.81
0.10
0.04
--
d1291
--
--
--
--
--
--
rl1304
356641
40.99
43.18
0.11
0.05
--
rl1323
370771
37.22
39.48
0.10
0.04
--
nrw1379
75506
33.31
33.88
0.11
0.05
--
fl1400
--
--
--
--
--
--
u1432
209329
36.84
37.23
0.13
0.05
--
fl1577
--
--
--
--
--
--
d1655
--
--
--
--
--
--
vm1748
--
--
--
--
--
--
u1817
--
--
--
--
--
--
rl1889
445401
40.71
42.89
0.15
0.06
--
d2103
--
--
--
--
--
--
u2152
--
--
--
--
--
--
u2319
311877
33.14
33.16
0.21
0.09
--
pr2392
526598
39.30
40.99
0.20
0.09
--
pcb3038
192052
39.48
40.61
0.28
0.13
--
fl3795
--
--
--
--
--
--
fnl4461
252112
38.09
38.85
0.37
0.17
--
rl5915
852814
50.80
53.15
0.53
0.24
--
rl5934
826194
48.58
50.64
0.53
0.24
--
pla7397
32558734
39.97
40.79
0.71
0.31
--
rl11849
--
--
--
--
--
--
usa13509
--
--
--
--
--
--
brd14051
648385
38.14
38.80
1.37
0.56
--
d15112
2156100
37.06
37.78
1.48
0.60
--
d18512
885927
37.30
37.97
1.84
0.72
--
pla33810
96027943
45.39
46.15
3.64
1.17
--
pla85900
205691535
44.46
45.05
11.46
2.81
--