ALGORITHM: Farthest-Insertion - 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
25981678
11.22
12.07
0.45
0.19
--
E1k.1
25455817
10.75
11.45
0.45
0.19
--
E1k.2
25593223
11.16
11.96
0.46
0.19
--
E1k.3
25935424
12.06
12.75
0.46
0.19
--
E1k.4
25393964
11.87
12.65
0.46
0.19
--
E1k.5
25888134
11.62
12.28
0.43
0.18
--
E1k.6
26469624
13.36
14.26
0.45
0.19
--
E1k.7
25418515
11.10
12.14
0.45
0.19
--
E1k.8
25805431
12.07
13.20
0.44
0.18
--
E1k.9
26143516
11.93
12.61
0.45
0.19
--
E3k.0
45476178
11.92
12.71
1.66
0.75
--
E3k.1
45144453
11.98
12.73
1.70
0.77
--
E3k.2
44905004
11.42
12.24
1.73
0.78
--
E3k.3
45299009
11.60
12.35
1.66
0.75
--
E3k.4
45441650
11.49
12.30
1.67
0.75
--
E10k.0
80965094
?
13.46
6.07
2.62
--
E10k.1
80987937
?
13.17
6.06
2.62
--
E10k.2
80932732
?
13.43
6.07
2.62
--
E31k.0
143443126
?
13.42
28.75
9.31
--
E31k.1
143689827
?
13.46
28.76
9.32
--
E100k.0
254580472
?
13.48
122.73
27.61
--
E100k.1
254085824
?
13.31
123.78
27.85
--
E316k.0
452117522
?
13.38
447.85
64.82
--
E1M.0
804189656
?
13.47
1725.72
316.38
--
E3M.0
1429977800
?
13.49
6663.34
1301.13
--
E10M.0
2542250220
?
13.49
24513.32
5344.71
--
C1k.0
12304502
8.05
8.64
0.50
0.21
--
C1k.1
12416593
9.14
9.58
0.51
0.21
--
C1k.2
11805630
8.76
9.22
0.54
0.22
--
C1k.3
13014079
9.49
10.07
0.51
0.21
--
C1k.4
12637550
9.89
10.53
0.52
0.22
--
C1k.5
12521060
9.88
10.52
0.52
0.22
--
C1k.6
11173168
9.90
10.71
0.48
0.20
--
C1k.7
11647007
9.21
9.85
0.50
0.21
--
C1k.8
12820224
10.46
10.84
0.53
0.22
--
C1k.9
11816998
8.34
9.05
0.51
0.21
--
C3k.0
21246002
10.67
11.35
1.90
0.86
--
C3k.1
20770173
9.21
9.89
1.86
0.84
--
C3k.2
21530014
10.14
10.92
1.79
0.81
--
C3k.3
21293423
11.43
12.06
1.87
0.84
--
C3k.4
21575501
14.37
15.02
1.95
0.88
--
C10k.0
37082924
?
13.12
6.91
2.99
--
C10k.1
36829297
?
11.74
6.55
2.83
--
C10k.2
37400197
?
13.59
6.91
2.99
--
C31k.0
67316252
?
13.77
30.70
9.95
--
C31k.1
66464840
?
12.96
30.29
9.81
--
C100k.0
118325891
?
13.87
133.28
29.99
--
C100k.1
119381340
?
14.06
135.29
30.44
--
C316k.0
211407334
?
13.92
487.97
70.63
--
M1k.0
--
--
--
--
--
--
M1k.1
--
--
--
--
--
--
M1k.2
--
--
--
--
--
--
M1k.3
--
--
--
--
--
--
M3k.0
--
--
--
--
--
--
M3k.1
--
--
--
--
--
--
M10k.0
--
--
--
--
--
--
dsj1000
20755271
11.23
11.91
0.47
0.19
--
pr1002
286683
10.67
11.65
0.49
0.20
--
si1032
--
--
--
--
--
--
u1060
--
--
--
--
--
--
vm1084
--
--
--
--
--
--
pcb1173
65501
15.13
16.24
0.57
0.24
--
d1291
--
--
--
--
--
--
rl1304
310246
22.65
24.55
0.62
0.26
--
rl1323
326644
20.89
22.88
0.64
0.27
--
nrw1379
62811
10.90
11.37
0.70
0.29
--
fl1400
--
--
--
--
--
--
u1432
173235
13.25
13.57
0.75
0.32
--
fl1577
--
--
--
--
--
--
d1655
--
--
--
--
--
--
vm1748
--
--
--
--
--
--
u1817
--
--
--
--
--
--
rl1889
371709
17.43
19.25
0.92
0.39
--
d2103
--
--
--
--
--
--
u2152
--
--
--
--
--
--
u2319
250062
6.75
6.77
1.27
0.55
--
pr2392
427610
13.11
14.49
1.24
0.54
--
pcb3038
158604
15.19
16.12
1.72
0.77
--
fl3795
--
--
--
--
--
--
fnl4461
203798
11.63
12.24
2.46
1.10
--
rl5915
693208
22.58
24.49
3.49
1.55
--
rl5934
669342
20.38
22.04
3.53
1.57
--
pla7397
26496949
13.91
14.57
4.58
2.01
--
rl11849
--
--
--
--
--
--
usa13509
--
--
--
--
--
--
brd14051
522358
11.29
11.82
10.32
4.25
--
d15112
1757611
11.73
12.32
11.49
4.67
--
d18512
720523
11.67
12.21
13.66
5.32
--
pla33810
77389916
17.17
17.78
30.69
9.84
--
pla85900
163529158
14.85
15.32
107.58
26.40
--