ALGORITHM: Nearest-Neighbor:JM 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
29803778
27.58
28.56
0.02
0.01
--
E1k.1
28909141
25.77
26.57
0.02
0.01
--
E1k.2
28643824
24.41
25.31
0.02
0.01
--
E1k.3
28736000
24.16
24.93
0.02
0.01
--
E1k.4
28137630
23.96
24.82
0.02
0.01
--
E1k.5
28973476
24.93
25.66
0.02
0.01
--
E1k.6
29096386
24.61
25.60
0.02
0.01
--
E1k.7
28952018
26.54
27.73
0.02
0.01
--
E1k.8
28279750
22.82
24.06
0.02
0.01
--
E1k.9
29305227
25.47
26.23
0.02
0.01
--
E3k.0
50903107
25.27
26.16
0.05
0.02
--
E3k.1
50246492
24.63
25.47
0.05
0.02
--
E3k.2
50410863
25.08
26.01
0.05
0.02
--
E3k.3
51233631
26.22
27.07
0.05
0.02
--
E3k.4
50224216
23.23
24.12
0.05
0.02
--
E10k.0
88804209
?
24.44
0.18
0.08
--
E10k.1
88533962
?
23.71
0.18
0.08
--
E10k.2
89091526
?
24.86
0.18
0.08
--
E31k.0
157045415
?
24.17
0.67
0.22
--
E31k.1
157492541
?
24.36
0.67
0.22
--
E100k.0
277495201
?
23.70
2.35
0.53
--
E100k.1
277746554
?
23.86
2.34
0.53
--
E316k.0
491771467
?
23.33
36.92
5.34
--
E1M.0
873714501
?
23.28
139.55
25.58
--
E3M.0
1549870782
?
23.01
530.26
103.54
--
E10M.0
2754227716
?
22.96
2078.86
453.26
--
C1k.0
14749518
29.52
30.23
0.02
0.01
--
C1k.1
14459672
27.10
27.61
0.02
0.01
--
C1k.2
13897322
28.03
28.57
0.02
0.01
--
C1k.3
14899430
25.35
26.01
0.02
0.01
--
C1k.4
14515536
26.22
26.95
0.02
0.01
--
C1k.5
14806828
29.94
30.70
0.02
0.01
--
C1k.6
12999358
27.86
28.80
0.02
0.01
--
C1k.7
13903644
30.37
31.13
0.02
0.01
--
C1k.8
14926068
28.61
29.05
0.02
0.01
--
C1k.9
14025082
28.59
29.43
0.02
0.01
--
C3k.0
25067434
30.57
31.38
0.05
0.02
--
C3k.1
25105974
32.01
32.82
0.05
0.02
--
C3k.2
25443263
30.16
31.08
0.05
0.02
--
C3k.3
25071578
31.21
31.95
0.05
0.02
--
C3k.4
24472983
29.73
30.47
0.05
0.02
--
C10k.0
43120482
?
31.54
0.19
0.08
--
C10k.1
43508292
?
32.01
0.19
0.08
--
C10k.2
42977794
?
30.52
0.19
0.08
--
C31k.0
77672003
?
31.27
0.67
0.22
--
C31k.1
78189896
?
32.89
0.67
0.22
--
C100k.0
137282080
?
32.11
2.33
0.52
--
C100k.1
138176447
?
32.02
2.35
0.53
--
C316k.0
244509866
?
31.76
36.72
5.31
--
M1k.0
--
--
--
--
--
--
M1k.1
--
--
--
--
--
--
M1k.2
--
--
--
--
--
--
M1k.3
--
--
--
--
--
--
M3k.0
--
--
--
--
--
--
M3k.1
--
--
--
--
--
--
M10k.0
--
--
--
--
--
--
dsj1000
24373883
30.62
31.42
0.02
0.01
--
pr1002
324652
25.33
26.44
0.02
0.01
--
si1032
--
--
--
--
--
--
u1060
--
--
--
--
--
--
vm1084
--
--
--
--
--
--
pcb1173
72316
27.11
28.33
0.02
0.01
--
d1291
--
--
--
--
--
--
rl1304
318928
26.08
28.04
0.02
0.01
--
rl1323
335549
24.19
26.23
0.02
0.01
--
nrw1379
70568
24.59
25.13
0.02
0.01
--
fl1400
--
--
--
--
--
--
u1432
194300
27.02
27.38
0.02
0.01
--
fl1577
--
--
--
--
--
--
d1655
--
--
--
--
--
--
vm1748
--
--
--
--
--
--
u1817
--
--
--
--
--
--
rl1889
399775
26.30
28.25
0.03
0.01
--
d2103
--
--
--
--
--
--
u2152
--
--
--
--
--
--
u2319
286780
22.42
22.44
0.03
0.01
--
pr2392
475496
25.78
27.31
0.04
0.02
--
pcb3038
174172
26.49
27.52
0.05
0.02
--
fl3795
--
--
--
--
--
--
fnl4461
226166
23.88
24.56
0.07
0.03
--
rl5915
696048
23.08
25.00
0.10
0.04
--
rl5934
678500
22.02
23.71
0.10
0.04
--
pla7397
29770744
27.99
28.73
0.12
0.05
--
rl11849
--
--
--
--
--
--
usa13509
--
--
--
--
--
--
brd14051
577300
22.99
23.59
0.28
0.12
--
d15112
1945361
23.67
24.31
0.31
0.13
--
d18512
790297
22.48
23.08
0.36
0.14
--
pla33810
82488581
24.89
25.54
0.67
0.21
--
pla85900
176008142
23.62
24.12
1.79
0.44
--