ALGORITHM: Double-Ended-Nearest-Neighbor (Bentley)

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
28534070
22.15
23.08
0.06
0.02
--
E1k.1
28080624
22.17
22.95
0.06
0.02
--
E1k.2
28308917
22.96
23.84
0.07
0.03
--
E1k.3
28510881
23.19
23.95
0.07
0.03
--
E1k.4
27883881
22.84
23.69
0.06
0.02
--
E1k.5
29943592
29.11
29.87
0.06
0.02
--
E1k.6
29375706
25.81
26.80
0.06
0.02
--
E1k.7
29082002
27.11
28.30
0.06
0.02
--
E1k.8
28633644
24.35
25.61
0.06
0.02
--
E1k.9
30267607
29.59
30.38
0.06
0.02
--
E3k.0
50006921
23.07
23.94
0.23
0.10
--
E3k.1
50567442
25.43
26.27
0.23
0.10
--
E3k.2
50063736
24.22
25.14
0.23
0.10
--
E3k.3
52174390
28.54
29.40
0.23
0.10
--
E3k.4
50533636
23.99
24.89
0.23
0.10
--
E10k.0
89028291
?
24.76
0.73
0.32
--
E10k.1
87583676
?
22.38
0.75
0.32
--
E10k.2
89082462
?
24.85
0.72
0.31
--
E31k.0
157160629
?
24.26
2.53
0.82
--
E31k.1
156362857
?
23.46
2.58
0.84
--
E100k.0
277054429
?
23.50
9.18
2.07
--
E100k.1
278164240
?
24.05
9.33
2.10
--
E316k.0
490426268
?
23.04
35.77
5.18
--
E1M.0
873053969
?
23.19
140.52
25.76
--
E3M.0
1549655440
?
22.99
523.45
102.21
--
E10M.0
2755191360
?
23.00
1857.59
405.02
--
C1k.0
15047038
32.14
32.86
0.07
0.03
--
C1k.1
14687809
29.10
29.63
0.07
0.03
--
C1k.2
14113998
30.02
30.57
0.07
0.03
--
C1k.3
14882330
25.20
25.87
0.06
0.02
--
C1k.4
14250294
23.92
24.63
0.07
0.03
--
C1k.5
14237792
24.95
25.68
0.07
0.03
--
C1k.6
12753641
25.45
26.37
0.07
0.03
--
C1k.7
14363194
34.68
35.46
0.06
0.02
--
C1k.8
14805013
27.57
28.00
0.06
0.02
--
C1k.9
13873416
27.20
28.03
0.06
0.02
--
C3k.0
24321842
26.69
27.47
0.23
0.10
--
C3k.1
24981958
31.36
32.17
0.24
0.11
--
C3k.2
25410511
29.99
30.91
0.23
0.10
--
C3k.3
24770875
29.63
30.37
0.22
0.10
--
C3k.4
24867950
31.83
32.58
0.23
0.10
--
C10k.0
42827328
?
30.64
0.72
0.31
--
C10k.1
42587598
?
29.21
0.73
0.32
--
C10k.2
42707651
?
29.70
0.72
0.31
--
C31k.0
77075825
?
30.26
2.49
0.81
--
C31k.1
78166015
?
32.84
2.54
0.82
--
C100k.0
136809484
?
31.65
9.16
2.06
--
C100k.1
137729714
?
31.59
9.14
2.06
--
C316k.0
243659694
?
31.30
35.54
5.14
--
M1k.0
--
--
--
--
--
--
M1k.1
--
--
--
--
--
--
M1k.2
--
--
--
--
--
--
M1k.3
--
--
--
--
--
--
M3k.0
--
--
--
--
--
--
M3k.1
--
--
--
--
--
--
M10k.0
--
--
--
--
--
--
dsj1000
23570360
26.31
27.08
0.06
0.02
--
pr1002
317056
22.39
23.48
0.06
0.02
--
si1032
--
--
--
--
--
--
u1060
--
--
--
--
--
--
vm1084
--
--
--
--
--
--
pcb1173
69752
22.60
23.78
0.08
0.03
--
d1291
--
--
--
--
--
--
rl1304
312790
23.66
25.57
0.09
0.04
--
rl1323
337482
24.90
26.96
0.08
0.03
--
nrw1379
70162
23.88
24.41
0.10
0.04
--
fl1400
--
--
--
--
--
--
u1432
191661
25.29
25.65
0.11
0.05
--
fl1577
--
--
--
--
--
--
d1655
--
--
--
--
--
--
vm1748
--
--
--
--
--
--
u1817
--
--
--
--
--
--
rl1889
397563
25.60
27.54
0.13
0.06
--
d2103
--
--
--
--
--
--
u2152
--
--
--
--
--
--
u2319
290021
23.81
23.83
0.17
0.07
--
pr2392
477315
26.26
27.80
0.16
0.07
--
pcb3038
171460
24.52
25.53
0.23
0.10
--
fl3795
--
--
--
--
--
--
fnl4461
226835
24.25
24.93
0.31
0.14
--
rl5915
696220
23.11
25.03
0.43
0.19
--
rl5934
678199
21.97
23.65
0.43
0.19
--
pla7397
29691146
27.64
28.39
0.56
0.25
--
rl11849
--
--
--
--
--
--
usa13509
--
--
--
--
--
--
brd14051
578741
23.30
23.89
1.11
0.46
--
d15112
1937479
23.16
23.81
1.21
0.49
--
d18512
798337
23.73
24.33
1.40
0.55
--
pla33810
81922013
24.03
24.68
2.80
0.90
--
pla85900
175410275
23.22
23.70
7.62
1.87
--