ALGORITHM: Convex-Hull-Greatest-Angle (kd-tree based 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
27575837
18.04
18.95
0.19
0.08
--
E1k.1
27333474
18.92
19.68
0.18
0.07
--
E1k.2
29182283
26.75
27.66
0.17
0.07
--
E1k.3
27597121
19.24
19.98
0.18
0.07
--
E1k.4
28424187
25.22
26.09
0.18
0.07
--
E1k.5
28785082
24.11
24.84
0.16
0.07
--
E1k.6
31425007
34.58
35.65
0.17
0.07
--
E1k.7
26902978
17.59
18.69
0.17
0.07
--
E1k.8
26639265
15.69
16.86
0.18
0.07
--
E1k.9
28442932
21.78
22.52
0.19
0.08
--
E3k.0
51440071
26.59
27.49
0.73
0.33
--
E3k.1
49230880
22.11
22.94
0.68
0.31
--
E3k.2
50363511
24.96
25.89
0.70
0.32
--
E3k.3
50850680
25.28
26.12
0.64
0.29
--
E3k.4
47966649
17.69
18.54
0.68
0.31
--
E10k.0
95241294
?
33.46
3.31
1.43
--
E10k.1
90391096
?
26.31
2.56
1.11
--
E10k.2
93939947
?
31.66
3.08
1.33
--
E31k.0
166056565
?
31.30
18.77
6.08
--
E31k.1
165299704
?
30.52
21.47
6.96
--
E100k.0
296665162
?
32.24
91.76
20.65
--
E100k.1
293506966
?
30.89
107.40
24.17
--
E316k.0
522646549
?
31.13
2729.17
395.01
--
E1M.0
928403554
?
31.00
15813.49
2899.14
--
E3M.0
1658552670
?
31.63
125867.37
24577.65
--
E10M.0
--
--
--
--
--
--
C1k.0
17296248
51.89
52.71
0.26
0.11
--
C1k.1
18390977
61.65
62.31
0.26
0.11
--
C1k.2
13472043
24.11
24.64
0.26
0.11
--
C1k.3
15498006
30.38
31.07
0.26
0.11
--
C1k.4
15065266
31.00
31.76
0.24
0.10
--
C1k.5
15161602
33.06
33.83
0.23
0.10
--
C1k.6
12464548
22.60
23.50
0.25
0.10
--
C1k.7
14071010
31.94
32.71
0.26
0.11
--
C1k.8
14766430
27.23
27.67
0.25
0.10
--
C1k.9
15334093
40.59
41.51
0.25
0.10
--
C3k.0
30231562
57.47
58.44
1.03
0.47
--
C3k.1
28705336
50.94
51.87
0.90
0.41
--
C3k.2
27442417
40.39
41.38
0.90
0.41
--
C3k.3
26863570
40.58
41.38
0.99
0.45
--
C3k.4
27461031
45.57
46.40
0.90
0.41
--
C10k.0
46647044
?
42.29
3.78
1.63
--
C10k.1
47517493
?
44.17
3.89
1.68
--
C10k.2
47860326
?
45.35
3.27
1.41
--
C31k.0
91675813
?
54.94
14.22
4.61
--
C31k.1
85103742
?
44.64
14.96
4.85
--
C100k.0
155092428
?
49.25
66.87
15.05
--
C100k.1
157474633
?
50.46
64.49
14.51
--
C316k.0
277196840
?
49.37
848.67
122.83
--
M1k.0
--
--
--
--
--
--
M1k.1
--
--
--
--
--
--
M1k.2
--
--
--
--
--
--
M1k.3
--
--
--
--
--
--
M3k.0
--
--
--
--
--
--
M3k.1
--
--
--
--
--
--
M10k.0
--
--
--
--
--
--
dsj1000
24087979
29.09
29.88
0.23
0.10
--
pr1002
295082
13.91
14.92
0.18
0.07
--
si1032
--
--
--
--
--
--
u1060
--
--
--
--
--
--
vm1084
--
--
--
--
--
--
pcb1173
70189
23.37
24.56
0.28
0.12
--
d1291
--
--
--
--
--
--
rl1304
311649
23.21
25.11
0.77
0.32
--
rl1323
337661
24.97
27.03
0.85
0.36
--
nrw1379
63646
12.37
12.86
0.24
0.10
--
fl1400
--
--
--
--
--
--
u1432
180082
17.72
18.06
0.51
0.21
--
fl1577
--
--
--
--
--
--
d1655
--
--
--
--
--
--
vm1748
--
--
--
--
--
--
u1817
--
--
--
--
--
--
rl1889
392338
23.95
25.87
1.36
0.58
--
d2103
--
--
--
--
--
--
u2152
--
--
--
--
--
--
u2319
251637
7.42
7.44
0.80
0.35
--
pr2392
458903
21.39
22.87
0.86
0.38
--
pcb3038
181083
31.51
32.58
0.92
0.41
--
fl3795
--
--
--
--
--
--
fnl4461
208297
14.09
14.72
1.02
0.46
--
rl5915
695849
23.04
24.96
16.79
7.45
--
rl5934
679910
22.28
23.96
13.12
5.82
--
pla7397
30707081
32.01
32.78
9.83
4.32
--
rl11849
--
--
--
--
--
--
usa13509
--
--
--
--
--
--
brd14051
584256
24.48
25.07
9.52
3.92
--
d15112
1975291
25.57
26.23
8.47
3.45
--
d18512
804577
24.70
25.30
5.91
2.30
--
pla33810
83942621
27.09
27.76
146.51
47.00
--
pla85900
174325257
22.45
22.93
804.85
197.51
--