ALGORITHM: Benchmark-Greedy

MACHINE: Compaq ES40 500 Mhz Alpha [ alpha500 ]

RUN: 1

SUBMITTER: Johnson-McGeoch

Instance
Tour Length
Percent over OPT
Percent over HK
Running Time (Seconds)
Normalized Time
Memory Usage (Megabytes)
E1k.0
27494385
17.70
18.60
0.02
0.02
--
E1k.1
26316209
14.49
15.22
0.02
0.02
--
E1k.2
26530429
15.23
16.06
0.02
0.02
--
E1k.3
27033547
16.81
17.53
0.02
0.02
--
E1k.4
26467511
16.60
17.41
0.02
0.02
--
E1k.5
26840234
15.73
16.41
0.02
0.02
--
E1k.6
28297348
21.19
22.15
0.02
0.02
--
E1k.7
27637102
20.80
21.93
0.02
0.02
--
E1k.8
26645986
15.72
16.89
0.02
0.02
--
E1k.9
27394231
17.29
18.00
0.02
0.02
--
E3k.0
47391812
16.63
17.46
0.07
0.07
--
E3k.1
47622395
18.12
18.92
0.07
0.07
--
E3k.2
46051871
14.26
15.11
0.07
0.07
--
E3k.3
47777886
17.71
18.50
0.07
0.07
--
E3k.4
47134097
15.65
16.49
0.07
0.07
--
E10k.0
83537327
?
17.06
0.25
0.25
--
E10k.1
83168578
?
16.21
0.25
0.25
--
E10k.2
82758628
?
15.99
0.25
0.25
--
E31k.0
146526854
?
15.85
1.00
1.00
--
E31k.1
145422817
?
14.83
1.00
1.00
--
E100k.0
257807924
?
14.92
4.50
4.50
--
E100k.1
256821944
?
14.53
4.50
4.50
--
E316k.0
456740686
?
14.54
20.00
20.00
23
E1M.0
809736269
?
14.26
89.00
89.00
69
E3M.0
1437010811
?
14.05
330.00
330.00
222
E10M.0
2552996838
?
13.97
1330.00
1330.00
723
C1k.0
13527321
18.79
19.44
0.02
0.02
--
C1k.1
13311373
17.01
17.48
0.02
0.02
--
C1k.2
12644039
16.48
16.98
0.02
0.02
--
C1k.3
13595325
14.38
14.98
0.02
0.02
--
C1k.4
13431002
16.79
17.47
0.02
0.02
--
C1k.5
13623888
19.56
20.26
0.02
0.02
--
C1k.6
12451976
22.48
23.38
0.02
0.02
--
C1k.7
13203805
23.81
24.53
0.02
0.02
--
C1k.8
13537979
16.65
17.05
0.02
0.02
--
C1k.9
13396357
22.82
23.63
0.02
0.02
--
C3k.0
23331536
21.53
22.28
0.07
0.07
--
C3k.1
22648198
19.09
19.82
0.07
0.07
--
C3k.2
23849029
22.01
22.86
0.07
0.07
--
C3k.3
23249611
21.67
22.36
0.07
0.07
--
C3k.4
22738893
20.54
21.23
0.07
0.07
--
C10k.0
40340699
?
23.06
0.25
0.25
--
C10k.1
40624419
?
23.26
0.25
0.25
--
C10k.2
40488062
?
22.96
0.25
0.25
--
C31k.0
71647819
?
21.09
0.98
0.98
--
C31k.1
71900525
?
22.20
0.97
0.97
--
C100k.0
126080352
?
21.33
4.50
4.50
--
C100k.1
127848640
?
22.15
4.50
4.50
--
C316k.0
225414603
?
21.47
20.10
20.10
--
M1k.0
5825718
185.93
185.96
1.56
1.56
--
M1k.1
5494766
157.97
158.04
1.57
1.57
--
M1k.2
5320658
150.94
150.97
1.58
1.58
--
M1k.3
5211599
157.46
157.49
1.57
1.57
--
M3k.0
6609767
219.04
219.04
16.70
16.70
--
M3k.1
5665811
176.50
176.51
16.50
16.50
--
M10k.0
7047065
249.63
249.65
169.00
169.00
--
dsj1000
21705226
16.32
17.03
0.02
0.02
--
pr1002
311124
20.10
21.17
0.03
0.03
--
si1032
93083
0.47
0.54
1.38
1.38
--
u1060
273380
21.99
22.78
0.03
0.03
--
vm1084
287818
20.28
21.87
0.02
0.02
--
pcb1173
67220
18.15
19.29
0.03
0.03
--
d1291
61979
22.00
23.44
0.03
0.03
--
rl1304
301783
19.31
21.15
0.03
0.03
--
rl1323
309811
14.66
16.55
0.02
0.02
--
nrw1379
66052
16.62
17.12
0.03
0.03
--
fl1400
24847
23.45
25.60
0.03
0.03
--
u1432
181841
18.87
19.21
0.03
0.03
--
fl1577
26327
18.33
20.29
0.03
0.03
--
d1655
72659
16.95
18.05
0.04
0.04
--
vm1748
398383
18.37
19.97
0.04
0.04
--
u1817
66999
17.13
18.19
0.04
0.04
--
rl1889
371663
17.42
19.24
0.05
0.05
--
d2103
91290
13.47
15.11
0.04
0.04
--
u2152
77521
20.65
21.40
0.05
0.05
--
u2319
266132
13.61
13.63
0.05
0.05
--
pr2392
454371
20.19
21.66
0.05
0.05
--
pcb3038
165064
19.88
20.85
0.07
0.07
--
fl3795
32465
12.84
14.00
0.08
0.08
--
fnl4461
212193
16.23
16.87
0.10
0.10
--
rl5915
635278
12.33
14.08
0.13
0.13
--
rl5934
632040
13.67
15.24
0.13
0.13
--
pla7397
27542328
18.41
19.09
0.14
0.14
--
rl11849
1045735
13.26
14.42
0.32
0.32
--
usa13509
23275260
16.48
17.25
0.38
0.38
--
brd14051
539237
14.88
15.44
0.35
0.35
--
d15112
1812900
15.24
15.85
0.40
0.40
--
d18512
740075
14.70
15.26
0.47
0.47
--
pla33810
77156494
16.82
17.43
0.73
0.73
--
pla85900
165433304
16.19
16.66
2.00
2.00
--