ALGORITHM: Benchmark Greedy

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
27494385
17.70
18.60
0.04
0.02
--
E1k.1
26316209
14.49
15.22
0.04
0.02
--
E1k.2
26530429
15.23
16.06
0.04
0.02
--
E1k.3
27033547
16.81
17.53
0.04
0.02
--
E1k.4
26467511
16.60
17.41
0.04
0.02
--
E1k.5
26840234
15.73
16.41
0.04
0.02
--
E1k.6
28297348
21.19
22.15
0.04
0.02
--
E1k.7
27637102
20.80
21.93
0.04
0.02
--
E1k.8
26645986
15.72
16.89
0.04
0.02
--
E1k.9
27394231
17.29
18.00
0.04
0.02
--
E3k.0
47391812
16.63
17.46
0.13
0.06
--
E3k.1
47622395
18.12
18.92
0.13
0.06
--
E3k.2
46051871
14.26
15.11
0.13
0.06
--
E3k.3
47777886
17.71
18.50
0.13
0.06
--
E3k.4
47134097
15.65
16.49
0.13
0.06
--
E10k.0
83537327
?
17.06
0.46
0.20
--
E10k.1
83168578
?
16.21
0.46
0.20
--
E10k.2
82758628
?
15.99
0.46
0.20
--
E31k.0
146526854
?
15.85
2.50
0.81
--
E31k.1
145422817
?
14.83
2.50
0.81
--
E100k.0
257807924
?
14.92
18.00
4.05
--
E100k.1
256821944
?
14.53
18.00
4.05
--
E316k.0
456740686
?
14.59
147.00
21.28
23
E1M.0
809736269
?
14.26
550.00
100.83
68
E3M.0
1437010811
?
14.05
1830.00
357.34
218
E10M.0
2552996838
?
13.97
6650.00
1449.92
707
C1k.0
13527321
18.79
19.44
0.04
0.02
--
C1k.1
13311373
17.01
17.48
0.04
0.02
--
C1k.2
12644039
16.48
16.98
0.04
0.02
--
C1k.3
13595325
14.38
14.98
0.04
0.02
--
C1k.4
13431002
16.79
17.47
0.04
0.02
--
C1k.5
13623888
19.56
20.26
0.04
0.02
--
C1k.6
12451976
22.48
23.38
0.04
0.02
--
C1k.7
13203805
23.81
24.53
0.04
0.02
--
C1k.8
13537979
16.65
17.05
0.04
0.02
--
C1k.9
13396357
22.82
23.63
0.04
0.02
--
C3k.0
23331536
21.53
22.28
0.13
0.06
--
C3k.1
22648198
19.09
19.82
0.13
0.06
--
C3k.2
23849029
22.01
22.86
0.13
0.06
--
C3k.3
23249611
21.67
22.36
0.13
0.06
--
C3k.4
22738893
20.54
21.23
0.13
0.06
--
C10k.0
40340699
?
23.06
0.46
0.20
--
C10k.1
40624419
?
23.26
0.47
0.20
--
C10k.2
40488062
?
22.96
0.47
0.20
--
C31k.0
71647819
?
21.09
2.80
0.91
--
C31k.1
71900525
?
22.20
2.80
0.91
--
C100k.0
126080352
?
21.33
19.00
4.28
--
C100k.1
127848640
?
22.15
19.00
4.28
--
C316k.0
225414603
?
21.47
134.00
19.39
--
M1k.0
5825718
185.93
185.96
1.80
0.74
--
M1k.1
5494766
157.97
158.04
1.80
0.74
--
M1k.2
5320658
150.94
150.97
1.80
0.74
--
M1k.3
5211599
157.46
157.49
1.80
0.74
--
M3k.0
6609767
219.04
219.04
20.00
9.03
--
M3k.1
5665811
176.50
176.51
19.00
8.58
--
M10k.0
7047065
249.63
249.65
247.00
106.81
--
dsj1000
21705226
16.32
17.03
0.04
0.02
--
pr1002
311124
20.10
21.17
0.04
0.02
--
si1032
93083
0.47
0.54
1.60
0.66
--
u1060
273380
21.99
22.78
0.05
0.02
--
vm1084
287818
20.28
21.87
0.05
0.02
--
pcb1173
67220
18.15
19.29
0.05
0.02
--
d1291
61979
22.00
23.44
0.05
0.02
--
rl1304
301783
19.31
21.15
0.06
0.03
--
rl1323
309811
14.66
16.55
0.06
0.03
--
nrw1379
66052
16.62
17.12
0.05
0.02
--
fl1400
24847
23.45
25.60
0.06
0.03
--
u1432
181841
18.87
19.21
0.05
0.02
--
fl1577
26327
18.33
20.29
0.06
0.03
--
d1655
72659
16.95
18.05
0.07
0.03
--
vm1748
398383
18.37
19.97
0.08
0.03
--
u1817
66999
17.13
18.19
0.07
0.03
--
rl1889
371663
17.42
19.24
0.08
0.03
--
d2103
91290
13.47
15.11
0.08
0.03
--
u2152
77521
20.65
21.40
0.09
0.04
--
u2319
266132
13.61
13.63
0.08
0.03
--
pr2392
454371
20.19
21.66
0.10
0.04
--
pcb3038
165064
19.88
20.85
0.13
0.06
--
fl3795
32465
12.84
14.00
0.15
0.07
--
fnl4461
212193
16.23
16.87
0.18
0.08
--
rl5915
635278
12.33
14.08
0.24
0.11
--
rl5934
632040
13.67
15.24
0.25
0.11
--
pla7397
27542328
18.41
19.09
0.25
0.11
--
rl11849
1045735
13.26
14.42
0.58
0.25
--
usa13509
23275260
16.48
17.25
0.69
0.29
--
brd14051
539237
14.88
15.44
0.64
0.26
--
d15112
1812900
15.24
15.85
0.72
0.29
--
d18512
740075
14.70
15.26
0.98
0.38
--
pla33810
77156494
16.82
17.43
1.40
0.45
--
pla85900
165433304
16.21
16.66
4.20
1.03
--