ALGORITHM: Double-MST heuristic implemented with kd-trees

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
32368523
38.56
39.62
0.06
0.02
--
E1k.1
31570906
37.35
38.23
0.06
0.02
--
E1k.2
31726447
37.80
38.79
0.06
0.02
--
E1k.3
31849771
37.62
38.47
0.06
0.02
--
E1k.4
31791144
40.06
41.03
0.06
0.02
--
E1k.5
32107198
38.44
39.25
0.06
0.02
--
E1k.6
31960789
36.88
37.96
0.06
0.02
--
E1k.7
31367284
37.10
38.38
0.06
0.02
--
E1k.8
31444978
36.56
37.94
0.06
0.02
--
E1k.9
32360355
38.55
39.39
0.06
0.02
--
E3k.0
56277954
38.50
39.48
0.19
0.09
--
E3k.1
55922377
38.71
39.65
0.20
0.09
--
E3k.2
56201162
39.45
40.48
0.19
0.09
--
E3k.3
56435201
39.04
39.97
0.20
0.09
--
E3k.4
56669388
39.04
40.05
0.20
0.09
--
E10k.0
99457794
?
39.37
0.74
0.32
--
E10k.1
100419193
?
40.32
0.77
0.33
--
E10k.2
99458097
?
39.39
0.75
0.32
--
E31k.0
177249035
?
40.15
2.93
0.95
--
E31k.1
177288060
?
39.99
2.97
0.96
--
E100k.0
314205822
?
40.06
13.07
2.94
--
E100k.1
313722339
?
39.90
13.02
2.93
--
E316k.0
557708169
?
39.92
164.36
23.79
--
E1M.0
992230815
?
40.01
552.96
101.38
--
E3M.0
1763373755
?
39.95
2000.08
390.55
--
E10M.0
3134149187
?
39.92
7407.39
1615.05
--
C1k.0
15249991
33.92
34.65
0.09
0.04
--
C1k.1
14972135
31.60
32.14
0.09
0.04
--
C1k.2
13956940
28.58
29.12
0.09
0.04
--
C1k.3
15888294
33.67
34.37
0.09
0.04
--
C1k.4
15554368
35.26
36.04
0.13
0.05
--
C1k.5
15303556
34.30
35.09
0.09
0.04
--
C1k.6
13585340
33.63
34.61
0.09
0.04
--
C1k.7
14474787
35.73
36.52
0.10
0.04
--
C1k.8
15542596
33.92
34.38
0.08
0.03
--
C1k.9
14324248
31.33
32.19
0.09
0.04
--
C3k.0
26066770
35.78
36.62
0.32
0.14
--
C3k.1
25784745
35.58
36.42
0.37
0.17
--
C3k.2
26970298
37.97
38.94
0.37
0.17
--
C3k.3
25779599
34.91
35.67
0.38
0.17
--
C3k.4
25846662
37.02
37.79
0.35
0.16
--
C10k.0
45166612
?
37.78
2.08
0.90
--
C10k.1
45297069
?
37.43
1.47
0.64
--
C10k.2
45207245
?
37.30
1.42
0.61
--
C31k.0
81655149
?
38.00
5.26
1.70
--
C31k.1
81445939
?
38.42
5.68
1.84
--
C100k.0
143863763
?
38.44
23.00
5.17
--
C100k.1
144773267
?
38.32
23.32
5.25
--
C316k.0
256577812
?
38.26
344.18
49.82
--
M1k.0
--
--
--
--
--
--
M1k.1
--
--
--
--
--
--
M1k.2
--
--
--
--
--
--
M1k.3
--
--
--
--
--
--
M3k.0
--
--
--
--
--
--
M3k.1
--
--
--
--
--
--
M10k.0
--
--
--
--
--
--
dsj1000
25223379
35.17
36.00
0.08
0.03
--
pr1002
338216
30.56
31.72
0.06
0.02
--
si1032
--
--
--
--
--
--
u1060
--
--
--
--
--
--
vm1084
--
--
--
--
--
--
pcb1173
79014
38.88
40.22
0.06
0.03
--
d1291
--
--
--
--
--
--
rl1304
366261
44.80
47.04
0.09
0.04
--
rl1323
396418
46.71
49.13
0.09
0.04
--
nrw1379
74345
31.26
31.83
0.07
0.03
--
fl1400
--
--
--
--
--
--
u1432
218146
42.61
43.01
0.07
0.03
--
fl1577
--
--
--
--
--
--
d1655
--
--
--
--
--
--
vm1748
--
--
--
--
--
--
u1817
--
--
--
--
--
--
rl1889
453562
43.29
45.51
0.12
0.05
--
d2103
--
--
--
--
--
--
u2152
--
--
--
--
--
--
u2319
359901
53.64
53.66
0.11
0.05
--
pr2392
508435
34.50
36.13
0.14
0.06
--
pcb3038
184761
34.18
35.27
0.18
0.08
--
fl3795
--
--
--
--
--
--
fnl4461
238803
30.80
31.52
0.26
0.12
--
rl5915
856392
51.43
53.79
0.45
0.20
--
rl5934
848771
52.64
54.75
0.45
0.20
--
pla7397
34077145
46.50
47.35
0.61
0.27
--
rl11849
--
--
--
--
--
--
usa13509
--
--
--
--
--
--
brd14051
619164
31.91
32.55
1.23
0.51
--
d15112
2141341
36.12
36.84
1.36
0.55
--
d18512
852278
32.09
32.73
1.50
0.58
--
pla33810
90811520
37.49
38.21
3.80
1.22
--
pla85900
201200333
41.33
41.88
11.98
2.94
--