ALGORITHM: Farthest-Augmented-Addition - Jon Bentley's 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
26013148
11.35
12.21
0.25
0.10
--
E1k.1
25470528
10.81
11.52
0.24
0.10
--
E1k.2
25693585
11.60
12.40
0.25
0.10
--
E1k.3
25991395
12.30
13.00
0.24
0.10
--
E1k.4
25465046
12.19
12.96
0.23
0.10
--
E1k.5
25906731
11.70
12.36
0.24
0.10
--
E1k.6
26536651
13.65
14.55
0.24
0.10
--
E1k.7
25446597
11.22
12.26
0.25
0.10
--
E1k.8
25822692
12.15
13.28
0.23
0.10
--
E1k.9
26155658
11.99
12.67
0.24
0.10
--
E3k.0
45525558
12.04
12.83
0.89
0.40
--
E3k.1
45178708
12.06
12.82
0.91
0.41
--
E3k.2
44968111
11.57
12.40
0.92
0.42
--
E3k.3
45390031
11.83
12.58
0.88
0.40
--
E3k.4
45492054
11.62
12.43
0.89
0.40
--
E10k.0
81071285
?
13.61
3.23
1.40
--
E10k.1
81134259
?
13.37
3.16
1.37
--
E10k.2
81043226
?
13.58
3.14
1.36
--
E31k.0
143679522
?
13.60
13.24
4.29
--
E31k.1
143944266
?
13.66
13.35
4.32
--
E100k.0
254979848
?
13.66
59.26
13.33
--
E100k.1
254455768
?
13.47
61.40
13.81
--
E316k.0
452789291
?
13.55
233.29
33.77
--
E1M.0
805334118
?
13.63
955.87
175.24
--
E3M.0
1432017780
?
13.65
3776.74
737.47
--
E10M.0
2545917660
?
13.66
14038.97
3060.96
--
C1k.0
12349466
8.45
9.04
0.25
0.10
--
C1k.1
12430415
9.26
9.70
0.24
0.10
--
C1k.2
11856439
9.23
9.69
0.26
0.11
--
C1k.3
13026359
9.59
10.17
0.25
0.10
--
C1k.4
12639627
9.91
10.55
0.26
0.11
--
C1k.5
12590411
10.49
11.14
0.24
0.10
--
C1k.6
11176700
9.93
10.74
0.24
0.10
--
C1k.7
11690127
9.62
10.25
0.24
0.10
--
C1k.8
12846727
10.69
11.07
0.24
0.10
--
C1k.9
11826335
8.43
9.14
0.24
0.10
--
C3k.0
21303949
10.97
11.65
0.93
0.42
--
C3k.1
20826066
9.51
10.18
0.95
0.43
--
C3k.2
21585660
10.43
11.20
0.89
0.40
--
C3k.3
21349855
11.73
12.36
0.90
0.41
--
C3k.4
21658787
14.82
15.47
0.95
0.43
--
C10k.0
37286992
?
13.74
3.20
1.38
--
C10k.1
36901505
?
11.96
3.15
1.36
--
C10k.2
37511909
?
13.92
3.23
1.40
--
C31k.0
67465043
?
14.02
13.28
4.30
--
C31k.1
66632768
?
13.24
13.30
4.31
--
C100k.0
118604137
?
14.13
60.96
13.72
--
C100k.1
119662137
?
14.33
62.25
14.01
--
C316k.0
211875941
?
14.17
235.41
34.07
--
M1k.0
--
--
--
--
--
--
M1k.1
--
--
--
--
--
--
M1k.2
--
--
--
--
--
--
M1k.3
--
--
--
--
--
--
M3k.0
--
--
--
--
--
--
M3k.1
--
--
--
--
--
--
M10k.0
--
--
--
--
--
--
dsj1000
20900073
12.00
12.69
0.24
0.10
--
pr1002
286878
10.74
11.73
0.25
0.10
--
si1032
--
--
--
--
--
--
u1060
--
--
--
--
--
--
vm1084
--
--
--
--
--
--
pcb1173
65580
15.27
16.38
0.31
0.13
--
d1291
--
--
--
--
--
--
rl1304
310620
22.80
24.70
0.30
0.13
--
rl1323
327060
21.04
23.04
0.33
0.14
--
nrw1379
62907
11.07
11.54
0.37
0.16
--
fl1400
--
--
--
--
--
--
u1432
173915
13.69
14.02
0.41
0.17
--
fl1577
--
--
--
--
--
--
d1655
--
--
--
--
--
--
vm1748
--
--
--
--
--
--
u1817
--
--
--
--
--
--
rl1889
373470
17.99
19.82
0.48
0.21
--
d2103
--
--
--
--
--
--
u2152
--
--
--
--
--
--
u2319
250268
6.84
6.85
0.74
0.32
--
pr2392
428095
13.24
14.62
0.67
0.29
--
pcb3038
158816
15.34
16.27
0.94
0.42
--
fl3795
--
--
--
--
--
--
fnl4461
203911
11.69
12.31
1.39
0.62
--
rl5915
694406
22.79
24.70
1.78
0.79
--
rl5934
669715
20.44
22.11
1.82
0.81
--
pla7397
26569331
14.22
14.89
2.49
1.09
--
rl11849
--
--
--
--
--
--
usa13509
--
--
--
--
--
--
brd14051
522782
11.38
11.91
5.14
2.12
--
d15112
1758853
11.81
12.40
5.72
2.33
--
d18512
721047
11.75
12.29
7.12
2.77
--
pla33810
77512491
17.36
17.97
14.88
4.77
--
pla85900
163772155
15.02
15.49
52.26
12.82
--