Instance
Held-Karp Bound
Optimal Tour Length
Percent Excess
E1k.0
23183212
23360648
0.77
E1k.1
22839568
22985695
0.64
E1k.2
22858726
23023351
0.72
E1k.3
23002034
23143748
0.62
E1k.4
22542849
22698717
0.69
E1k.5
23057465
23192391
0.59
E1k.6
23166620
23349803
0.79
E1k.7
22666814
22879091
0.94
E1k.8
22795477
23025754
1.01
E1k.9
23215285
23356256
0.61
E3k.0
40348236
40634081
0.71
E3k.1
40046054
40315287
0.67
E3k.2
40006528
40303394
0.74
E3k.3
40318841
40589659
0.67
E3k.4
40462881
40757209
0.73
E10k.0
71362276
--
--
E10k.1
71565485
--
--
E10k.2
71351795
--
--
E31k.0
126474847
--
--
E31k.1
126647285
--
--
E100k.0
224330692
--
--
E100k.1
224241789
--
--
E316k.0
398582616
--
--
E1M.0
708703513
--
--
E3M.0
1260000000
--
--
E10M.0
2240000000
--
--
C1k.0
11325840
11387430
0.54
C1k.1
11330836
11376735
0.41
C1k.2
10809149
10855033
0.42
C1k.3
11823906
11886457
0.53
C1k.4
11433764
11499958
0.58
C1k.5
11328719
11394911
0.58
C1k.6
10092637
10166701
0.73
C1k.7
10602996
10664660
0.58
C1k.8
11566102
11605723
0.34
C1k.9
10835951
10906997
0.66
C3k.0
19080351
19198258
0.62
C3k.1
18901572
19017805
0.61
C3k.2
19410947
19547551
0.70
C3k.3
19001116
19108508
0.57
C3k.4
18757585
18864046
0.57
C10k.0
32782155
--
--
C10k.1
32958946
--
--
C10k.2
32926889
--
--
C31k.0
59169193
--
--
C31k.1
58840096
--
--
C100k.0
103916254
--
--
C100k.1
104663040
--
--
C316k.0
185576667
--
--
M1k.0
2037215
2037498
0.01
M1k.1
2129383
2130002
0.03
M1k.2
2120078
2120310
0.01
M1k.3
2023998
2024198
0.01
M3k.0
2071735
2071765
0.00
M3k.1
2049010
2049127
0.01
M10k.0
2015488
2015568
0.00
dsj1000
18546977
18660188
0.61
pr1002
256766
259045
0.89
si1032
92579
92650
0.08
u1060
222651
224094
0.65
vm1084
236162
239297
1.33
pcb1173
56351
56892
0.96
d1291
50209
50801
1.18
rl1304
249094
252948
1.55
rl1323
265814
270199
1.65
nrw1379
56396
56638
0.43
fl1400
19783
20127
1.74
u1432
152535
152970
0.29
fl1577
21886
22249
1.66
d1655
61549
62128
0.94
vm1748
332061
336556
1.35
u1817
56688
57201
0.90
rl1889
311704
316536
1.55
d2103
79307
80450
1.44
u2152
63858
64253
0.62
u2319
234215
234256
0.02
pr2392
373490
378032
1.22
pcb3038
136588
137694
0.81
fl3795
28477
28772
1.04
fnl4461
181569
182566
0.55
rl5915
556849
565530
1.56
rl5934
548471
556045
1.38
pla7397
23126464
23260728
0.58
rl11849
913980
923288
1.02
usa13509
19851464
19982859
0.66
brd14051
467128
469385
0.48
d15112
1564880
1573084
0.52
d18512
642117
645238
0.49
pla33810
65705438
66048945
0.52
pla85900
141806385
142382641
0.41