ALGORITHM: Quick-Boruvka - Concorde's implementation

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
27403471
17.31
18.20
0.03
0.01
--
E1k.1
26875598
16.92
17.67
0.03
0.01
--
E1k.2
27437515
19.17
20.03
0.03
0.01
--
E1k.3
26988987
16.61
17.33
0.03
0.01
--
E1k.4
26947281
18.72
19.54
0.03
0.01
--
E1k.5
27843749
20.06
20.76
0.03
0.01
--
E1k.6
27008626
15.67
16.58
0.03
0.01
--
E1k.7
27154685
18.69
19.80
0.03
0.01
--
E1k.8
27116464
17.77
18.96
0.03
0.01
--
E1k.9
27605175
18.19
18.91
0.03
0.01
--
E3k.0
47811851
17.66
18.50
0.08
0.04
--
E3k.1
47646358
18.18
18.98
0.08
0.04
--
E3k.2
47304252
17.37
18.24
0.08
0.04
--
E3k.3
47641349
17.37
18.16
0.08
0.04
--
E3k.4
47280947
16.01
16.85
0.08
0.04
--
E10k.0
83588348
?
17.13
0.27
0.12
--
E10k.1
83600758
?
16.82
0.27
0.12
--
E10k.2
83085783
?
16.45
0.27
0.12
--
E31k.0
146709334
?
16.00
0.95
0.31
--
E31k.1
146869449
?
15.97
0.96
0.31
--
E100k.0
258686950
?
15.32
5.08
1.14
--
E100k.1
259347347
?
15.66
5.04
1.13
--
E316k.0
460113587
?
15.39
27.77
4.02
--
E1M.0
816698466
?
15.24
121.93
22.35
--
E3M.0
1449200771
?
15.02
492.48
96.16
--
E10M.0
2575275297
?
14.97
1854.21
404.28
--
C1k.0
14754570
29.57
30.27
0.03
0.01
--
C1k.1
14428325
26.82
27.34
0.03
0.01
--
C1k.2
14146074
30.32
30.87
0.03
0.01
--
C1k.3
14335156
20.60
21.24
0.03
0.01
--
C1k.4
14587946
26.85
27.59
0.03
0.01
--
C1k.5
14062666
23.41
24.13
0.03
0.01
--
C1k.6
12182715
19.83
20.71
0.03
0.01
--
C1k.7
13493362
26.52
27.26
0.03
0.01
--
C1k.8
14270711
22.96
23.38
0.03
0.01
--
C1k.9
12989580
19.09
19.87
0.03
0.01
--
C3k.0
23859423
24.28
25.05
0.08
0.04
--
C3k.1
23079811
21.36
22.11
0.08
0.04
--
C3k.2
24679657
26.25
27.14
0.08
0.04
--
C3k.3
23766247
24.38
25.08
0.08
0.04
--
C3k.4
24175747
28.16
28.89
0.08
0.04
--
C10k.0
40511655
?
23.58
0.27
0.12
--
C10k.1
40755522
?
23.66
0.27
0.12
--
C10k.2
41570257
?
26.25
0.26
0.11
--
C31k.0
73603373
?
24.39
0.93
0.30
--
C31k.1
73594793
?
25.08
0.92
0.30
--
C100k.0
128756116
?
23.90
4.84
1.09
--
C100k.1
129953779
?
24.16
4.88
1.10
--
C316k.0
229671418
?
23.76
26.16
3.79
--
M1k.0
--
--
--
--
--
--
M1k.1
--
--
--
--
--
--
M1k.2
--
--
--
--
--
--
M1k.3
--
--
--
--
--
--
M3k.0
--
--
--
--
--
--
M3k.1
--
--
--
--
--
--
M10k.0
--
--
--
--
--
--
dsj1000
22700675
21.65
22.40
0.03
0.01
--
pr1002
311188
20.13
21.20
0.03
0.01
--
si1032
311188
235.87
236.13
1.84
0.76
--
u1060
267012
19.15
19.92
0.04
0.02
--
vm1084
292977
22.43
24.06
0.04
0.02
--
pcb1173
65321
14.82
15.92
0.04
0.02
--
d1291
57697
13.57
14.91
0.04
0.02
--
rl1304
300826
18.93
20.77
0.04
0.02
--
rl1323
327940
21.37
23.37
0.04
0.02
--
nrw1379
66136
16.77
17.27
0.04
0.02
--
fl1400
26527
31.80
34.09
0.04
0.02
--
u1432
183446
19.92
20.26
0.04
0.02
--
fl1577
27598
24.04
26.10
0.05
0.02
--
d1655
74449
19.83
20.96
0.05
0.02
--
vm1748
396735
17.88
19.48
0.05
0.02
--
u1817
65711
14.88
15.92
0.05
0.02
--
rl1889
383198
21.06
22.94
0.06
0.03
--
d2103
88187
9.62
11.20
0.06
0.03
--
u2152
75989
18.27
19.00
0.06
0.03
--
u2319
264323
12.84
12.85
0.07
0.03
--
pr2392
456121
20.66
22.12
0.08
0.04
--
pcb3038
162967
18.35
19.31
0.10
0.04
--
fl3795
36241
25.96
27.26
0.11
0.05
--
fnl4461
209486
14.75
15.38
0.11
0.05
--
rl5915
651143
15.14
16.93
0.17
0.08
--
rl5934
641076
15.29
16.88
0.17
0.08
--
pla7397
28087300
20.75
21.45
0.19
0.08
--
rl11849
1072290
16.14
17.32
0.35
0.15
--
usa13509
23418475
17.19
17.97
0.39
0.16
--
brd14051
546043
16.33
16.89
0.37
0.15
--
d15112
1789564
13.76
14.36
0.41
0.17
--
d18512
739956
14.68
15.24
0.51
0.20
--
pla33810
78358164
18.64
19.26
0.96
0.31
--
pla85900
164536012
15.56
16.03
2.78
0.68
--