ALGORITHM: Nearest-Neighbor - 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
29876834
27.89
28.87
0.03
0.01
--
E1k.1
28826885
25.41
26.21
0.03
0.01
--
E1k.2
28990467
25.92
26.82
0.03
0.01
--
E1k.3
28919803
24.96
25.73
0.03
0.01
--
E1k.4
27908954
22.95
23.80
0.03
0.01
--
E1k.5
28129950
21.29
22.00
0.03
0.01
--
E1k.6
28315437
21.27
22.23
0.03
0.01
--
E1k.7
29136526
27.35
28.54
0.03
0.01
--
E1k.8
28894147
25.49
26.75
0.03
0.01
--
E1k.9
29066593
24.45
25.20
0.03
0.01
--
E3k.0
50808700
25.04
25.93
0.07
0.03
--
E3k.1
50225733
24.58
25.42
0.07
0.03
--
E3k.2
50050793
24.19
25.11
0.07
0.03
--
E3k.3
50654060
24.80
25.63
0.07
0.03
--
E3k.4
50054191
22.81
23.70
0.07
0.03
--
E10k.0
87023393
?
21.95
0.25
0.11
--
E10k.1
88223334
?
23.28
0.24
0.10
--
E10k.2
89459437
?
25.38
0.24
0.10
--
E31k.0
155756544
?
23.15
0.82
0.27
--
E31k.1
158038881
?
24.79
0.79
0.26
--
E100k.0
276607762
?
23.30
3.91
0.88
--
E100k.1
278736560
?
24.30
3.87
0.87
--
E316k.0
492073104
?
23.46
18.84
2.73
--
E1M.0
874090989
?
23.34
77.33
14.18
--
E3M.0
1550120396
?
23.03
300.14
58.61
--
E10M.0
2754560464
?
22.97
1133.82
247.21
--
C1k.0
14447303
26.87
27.56
0.03
0.01
--
C1k.1
14762298
29.76
30.28
0.03
0.01
--
C1k.2
13694756
26.16
26.70
0.03
0.01
--
C1k.3
14862341
25.04
25.70
0.03
0.01
--
C1k.4
14454908
25.70
26.42
0.03
0.01
--
C1k.5
14857057
30.38
31.15
0.03
0.01
--
C1k.6
13279282
30.62
31.57
0.03
0.01
--
C1k.7
13156534
23.37
24.08
0.03
0.01
--
C1k.8
14875441
28.17
28.61
0.03
0.01
--
C1k.9
13997313
28.33
29.17
0.03
0.01
--
C3k.0
25236988
31.45
32.27
0.07
0.03
--
C3k.1
25680100
35.03
35.86
0.07
0.03
--
C3k.2
25841067
32.20
33.13
0.07
0.03
--
C3k.3
24950009
30.57
31.31
0.07
0.03
--
C3k.4
24652890
30.69
31.43
0.07
0.03
--
C10k.0
43145586
?
31.61
0.23
0.10
--
C10k.1
42702234
?
29.56
0.25
0.11
--
C10k.2
43744935
?
32.85
0.23
0.10
--
C31k.0
77475389
?
30.94
0.81
0.26
--
C31k.1
78297258
?
33.07
0.80
0.26
--
C100k.0
136726553
?
31.57
3.94
0.89
--
C100k.1
138006425
?
31.86
3.99
0.90
--
C316k.0
244360006
?
31.68
18.34
2.65
--
M1k.0
6420257
215.10
215.15
1.94
0.80
--
M1k.1
6586003
209.20
209.29
1.93
0.80
--
M1k.2
6710496
216.49
216.52
1.94
0.80
--
M1k.3
7214338
256.40
256.44
1.93
0.80
--
M3k.0
8862429
327.77
327.78
21.51
9.71
--
M3k.1
8467884
313.24
313.27
21.54
9.73
--
M10k.0
8816401
337.42
337.43
259.55
112.24
--
dsj1000
24718012
32.46
33.27
0.03
0.01
--
pr1002
312691
20.71
21.78
0.03
0.01
--
si1032
94381
1.87
1.95
1.86
0.77
--
u1060
299527
33.66
34.53
0.03
0.01
--
vm1084
299538
25.17
26.84
0.03
0.01
--
pcb1173
72969
28.26
29.49
0.04
0.02
--
d1291
63753
25.50
26.98
0.04
0.02
--
rl1304
325331
28.62
30.61
0.04
0.02
--
rl1323
345973
28.04
30.16
0.04
0.02
--
nrw1379
69788
23.22
23.75
0.04
0.02
--
fl1400
26771
33.01
35.32
0.04
0.02
--
u1432
191041
24.89
25.24
0.04
0.02
--
fl1577
27445
23.35
25.40
0.05
0.02
--
d1655
75255
21.13
22.27
0.05
0.02
--
vm1748
428060
27.19
28.91
0.05
0.02
--
u1817
71924
25.74
26.88
0.05
0.02
--
rl1889
385967
21.93
23.82
0.05
0.02
--
d2103
92399
14.85
16.51
0.06
0.03
--
u2152
82093
27.77
28.56
0.06
0.03
--
u2319
287440
22.70
22.72
0.06
0.03
--
pr2392
469774
24.27
25.78
0.07
0.03
--
pcb3038
173241
25.82
26.84
0.08
0.04
--
fl3795
36325
26.25
27.56
0.10
0.04
--
fnl4461
226913
24.29
24.97
0.10
0.04
--
rl5915
698423
23.50
25.42
0.15
0.07
--
rl5934
671574
20.78
22.44
0.15
0.07
--
pla7397
29254018
25.77
26.50
0.16
0.07
--
rl11849
1115912
20.86
22.09
0.32
0.14
--
usa13509
25044488
25.33
26.16
0.36
0.15
--
brd14051
577354
23.00
23.60
0.32
0.13
--
d15112
1961081
24.66
25.32
0.34
0.14
--
d18512
787643
22.07
22.66
0.44
0.17
--
pla33810
81906409
24.01
24.66
0.82
0.26
--
pla85900
175663983
23.39
23.88
2.35
0.58
--