ALGORITHM: Best-Way-Strip algorithm, best of x- and y-direction strips, 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.02
0.01
--
E1k.1
29534850
28.49
29.31
0.01
0.00
--
E1k.2
29906404
29.90
30.83
0.02
0.01
--
E1k.3
30196648
30.47
31.28
0.01
0.00
--
E1k.4
29728119
30.97
31.87
0.01
0.00
--
E1k.5
29804058
28.51
29.26
0.01
0.00
--
E1k.6
30333422
29.91
30.94
0.02
0.01
--
E1k.7
30181486
31.92
33.15
0.01
0.00
--
E1k.8
30108411
30.76
32.08
0.01
0.00
--
E1k.9
30534428
30.73
31.53
0.02
0.01
--
E3k.0
53154352
30.81
31.74
0.06
0.03
--
E3k.1
52849556
31.09
31.97
0.06
0.03
--
E3k.2
52624723
30.57
31.54
0.06
0.03
--
E3k.3
53123081
30.88
31.76
0.06
0.03
--
E3k.4
53125323
30.35
31.29
0.06
0.03
--
E10k.0
93017765
?
30.35
0.13
0.06
--
E10k.1
93358766
?
30.45
0.12
0.05
--
E10k.2
92547368
?
29.71
0.12
0.05
--
E31k.0
164721114
?
30.24
0.36
0.12
--
E31k.1
164726354
?
30.07
0.37
0.12
--
E100k.0
292250436
?
30.28
1.16
0.26
--
E100k.1
292417999
?
30.40
1.18
0.27
--
E316k.0
518981908
?
30.21
5.63
0.81
--
E1M.0
922025850
?
30.10
24.62
4.51
--
E3M.0
1639105096
?
30.09
89.65
17.51
--
E10M.0
2913959139
?
30.09
322.88
70.40
--
C1k.0
23985196
110.63
111.77
0.02
0.01
--
C1k.1
22530831
98.04
98.85
0.01
0.00
--
C1k.2
22914281
111.09
111.99
0.01
0.00
--
C1k.3
26495289
122.90
124.08
0.02
0.01
--
C1k.4
25824965
124.57
125.87
0.02
0.01
--
C1k.5
23513412
106.35
107.56
0.02
0.01
--
C1k.6
17628141
73.39
74.66
0.02
0.01
--
C1k.7
22365059
109.71
110.93
0.02
0.01
--
C1k.8
24881690
114.39
115.13
0.01
0.00
--
C1k.9
23405764
114.59
116.00
0.02
0.01
--
C3k.0
46555350
142.50
144.00
0.06
0.03
--
C3k.1
47138704
147.87
149.39
0.06
0.03
--
C3k.2
49627135
153.88
155.67
0.06
0.03
--
C3k.3
46964575
145.78
147.17
0.06
0.03
--
C3k.4
45319827
140.24
141.61
0.06
0.03
--
C10k.0
92220547
?
181.31
0.13
0.06
--
C10k.1
89710417
?
172.19
0.14
0.06
--
C10k.2
88671265
?
169.30
0.13
0.06
--
C31k.0
171248813
?
189.42
0.36
0.12
--
C31k.1
171705391
?
191.82
0.36
0.12
--
C100k.0
310835932
?
199.12
1.17
0.26
--
C100k.1
309256914
?
195.48
1.16
0.26
--
C316k.0
559993367
?
201.76
5.66
0.82
--
M1k.0
--
--
--
--
--
--
M1k.1
--
--
--
--
--
--
M1k.2
--
--
--
--
--
--
M1k.3
--
--
--
--
--
--
M3k.0
--
--
--
--
--
--
M3k.1
--
--
--
--
--
--
M10k.0
--
--
--
--
--
--
dsj1000
31597896
69.33
70.37
0.01
0.00
--
pr1002
394289
52.21
53.56
0.01
0.00
--
si1032
--
--
--
--
--
--
u1060
--
--
--
--
--
--
vm1084
--
--
--
--
--
--
pcb1173
73779
29.68
30.93
0.01
0.00
--
d1291
--
--
--
--
--
--
rl1304
395731
56.45
58.87
0.02
0.01
--
rl1323
397495
47.11
49.54
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
518485
63.80
66.34
0.02
0.01
--
d2103
--
--
--
--
--
--
u2152
--
--
--
--
--
--
u2319
265591
13.38
13.40
0.04
0.02
--
pr2392
556394
47.18
48.97
0.04
0.02
--
pcb3038
175203
27.24
28.27
0.04
0.02
--
fl3795
--
--
--
--
--
--
fnl4461
238859
30.83
31.55
0.06
0.03
--
rl5915
849218
50.16
52.50
0.07
0.03
--
rl5934
851221
53.08
55.20
0.07
0.03
--
pla7397
46492337
99.87
101.04
0.09
0.04
--
rl11849
--
--
--
--
--
--
usa13509
--
--
--
--
--
--
brd14051
677475
44.34
45.03
0.16
0.07
--
d15112
2246528
42.81
43.56
0.17
0.07
--
d18512
867576
34.46
35.11
0.20
0.08
--
pla33810
113183727
71.36
72.26
0.36
0.12
--
pla85900
234930199
65.03
65.67
0.96
0.24
--