ALGORITHM: Strip algorithm with initial sorting in x direction, radix sort

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
30697456
31.41
32.41
0.01
0.00
--
E1k.1
29534850
28.49
29.31
0.00
0.00
--
E1k.2
29906404
29.90
30.83
0.01
0.00
--
E1k.3
30375183
31.25
32.05
0.00
0.00
--
E1k.4
30099004
32.60
33.52
0.00
0.00
--
E1k.5
30027557
29.47
30.23
0.00
0.00
--
E1k.6
30333422
29.91
30.94
0.01
0.00
--
E1k.7
30880113
34.97
36.23
0.00
0.00
--
E1k.8
30160055
30.98
32.31
0.00
0.00
--
E1k.9
30534428
30.73
31.53
0.01
0.00
--
E3k.0
53154352
30.81
31.74
0.04
0.02
--
E3k.1
52906399
31.23
32.11
0.04
0.02
--
E3k.2
53708104
33.26
34.25
0.04
0.02
--
E3k.3
53123081
30.88
31.76
0.04
0.02
--
E3k.4
53125323
30.35
31.29
0.04
0.02
--
E10k.0
94051672
?
31.79
0.10
0.04
--
E10k.1
93565019
?
30.74
0.08
0.03
--
E10k.2
92547368
?
29.71
0.08
0.03
--
E31k.0
164721114
?
30.24
0.27
0.09
--
E31k.1
164726354
?
30.07
0.27
0.09
--
E100k.0
292364628
?
30.33
0.85
0.19
--
E100k.1
292417999
?
30.40
0.87
0.20
--
E316k.0
519028260
?
30.22
3.67
0.53
--
E1M.0
922025850
?
30.10
15.09
2.77
--
E3M.0
1639198857
?
30.10
53.44
10.44
--
E10M.0
2913959139
?
30.09
188.96
41.20
--
C1k.0
23985196
110.63
111.77
0.01
0.00
--
C1k.1
25092191
120.56
121.45
0.01
0.00
--
C1k.2
22914281
111.09
111.99
0.00
0.00
--
C1k.3
26495289
122.90
124.08
0.01
0.00
--
C1k.4
26023414
126.29
127.60
0.01
0.00
--
C1k.5
23513412
106.35
107.56
0.01
0.00
--
C1k.6
17628141
73.39
74.66
0.01
0.00
--
C1k.7
22365059
109.71
110.93
0.01
0.00
--
C1k.8
28893890
148.96
149.82
0.00
0.00
--
C1k.9
23428425
114.80
116.21
0.02
0.01
--
C3k.0
49119041
155.85
157.43
0.04
0.02
--
C3k.1
51027172
168.31
169.96
0.04
0.02
--
C3k.2
49627135
153.88
155.67
0.04
0.02
--
C3k.3
51005450
166.93
168.43
0.04
0.02
--
C3k.4
47378989
151.16
152.59
0.04
0.02
--
C10k.0
92345072
?
181.69
0.10
0.04
--
C10k.1
89710417
?
172.19
0.10
0.04
--
C10k.2
88671265
?
169.30
0.10
0.04
--
C31k.0
171248813
?
189.42
0.27
0.09
--
C31k.1
171705391
?
191.82
0.27
0.09
--
C100k.0
311155490
?
199.43
0.86
0.19
--
C100k.1
310504894
?
196.67
0.85
0.19
--
C316k.0
559993367
?
201.76
3.69
0.53
--
M1k.0
--
--
--
--
--
--
M1k.1
--
--
--
--
--
--
M1k.2
--
--
--
--
--
--
M1k.3
--
--
--
--
--
--
M3k.0
--
--
--
--
--
--
M3k.1
--
--
--
--
--
--
M10k.0
--
--
--
--
--
--
dsj1000
31597896
69.33
70.37
0.00
0.00
--
pr1002
394289
52.21
53.56
0.00
0.00
--
si1032
--
--
--
--
--
--
u1060
--
--
--
--
--
--
vm1084
--
--
--
--
--
--
pcb1173
73779
29.68
30.93
0.00
0.00
--
d1291
--
--
--
--
--
--
rl1304
553358
118.76
122.15
0.02
0.01
--
rl1323
546842
102.38
105.72
0.02
0.01
--
nrw1379
78199
38.07
38.66
0.02
0.01
--
fl1400
--
--
--
--
--
--
u1432
191731
25.34
25.70
0.02
0.01
--
fl1577
--
--
--
--
--
--
d1655
--
--
--
--
--
--
vm1748
--
--
--
--
--
--
u1817
--
--
--
--
--
--
rl1889
643133
103.18
106.33
0.01
0.00
--
d2103
--
--
--
--
--
--
u2152
--
--
--
--
--
--
u2319
265591
13.38
13.40
0.02
0.01
--
pr2392
556394
47.18
48.97
0.02
0.01
--
pcb3038
175203
27.24
28.27
0.03
0.01
--
fl3795
--
--
--
--
--
--
fnl4461
238859
30.83
31.55
0.04
0.02
--
rl5915
1219473
115.63
119.00
0.05
0.02
--
rl5934
1179904
112.20
115.13
0.05
0.02
--
pla7397
46492337
99.87
101.04
0.06
0.03
--
rl11849
--
--
--
--
--
--
usa13509
--
--
--
--
--
--
brd14051
677475
44.34
45.03
0.11
0.05
--
d15112
2246528
42.81
43.56
0.13
0.05
--
d18512
867576
34.46
35.11
0.15
0.06
--
pla33810
126059923
90.86
91.86
0.28
0.09
--
pla85900
245729053
72.61
73.28
0.73
0.18
--