ALGORITHM: Random-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
26264772
12.43
13.29
0.37
0.15
--
E1k.1
26217757
14.06
14.79
0.37
0.15
--
E1k.2
26433403
14.81
15.64
0.38
0.16
--
E1k.3
26033069
12.48
13.18
0.38
0.16
--
E1k.4
25955121
14.35
15.14
0.37
0.15
--
E1k.5
26338468
13.57
14.23
0.37
0.15
--
E1k.6
26430733
13.19
14.09
0.37
0.15
--
E1k.7
26103996
14.10
15.16
0.37
0.15
--
E1k.8
26173504
13.67
14.82
0.36
0.15
--
E1k.9
26216228
12.24
12.93
0.36
0.15
--
E3k.0
46486018
14.40
15.21
1.35
0.61
--
E3k.1
45691373
13.34
14.10
1.32
0.60
--
E3k.2
45997562
14.13
14.98
1.34
0.61
--
E3k.3
45655554
12.48
13.24
1.34
0.61
--
E3k.4
45986901
12.83
13.65
1.36
0.61
--
E10k.0
81962539
?
14.85
4.54
1.96
--
E10k.1
82002154
?
14.58
4.68
2.02
--
E10k.2
81431168
?
14.13
4.48
1.94
--
E31k.0
145773000
?
15.26
21.27
6.89
--
E31k.1
145573919
?
14.94
21.33
6.91
--
E100k.0
257958206
?
14.99
89.64
20.17
--
E100k.1
257966801
?
15.04
90.58
20.38
--
E316k.0
458518016
?
14.99
311.57
45.10
--
E1M.0
815907586
?
15.13
1106.88
202.93
--
E3M.0
1449766130
?
15.06
3974.51
776.09
--
E10M.0
2577708000
?
15.08
14023.31
3057.54
--
C1k.0
12720900
11.71
12.32
0.42
0.17
--
C1k.1
12754472
12.11
12.56
0.46
0.19
--
C1k.2
12236191
12.72
13.20
0.45
0.19
--
C1k.3
13116087
10.34
10.93
0.43
0.18
--
C1k.4
12774522
11.08
11.73
0.43
0.18
--
C1k.5
12626568
10.81
11.46
0.41
0.17
--
C1k.6
11345232
11.59
12.41
0.42
0.17
--
C1k.7
12059349
13.08
13.74
0.44
0.18
--
C1k.8
12757719
9.93
10.30
0.41
0.17
--
C1k.9
12124949
11.17
11.90
0.41
0.17
--
C3k.0
21363310
11.28
11.96
1.52
0.69
--
C3k.1
21226083
11.61
12.30
1.52
0.69
--
C3k.2
21727081
11.15
11.93
1.48
0.67
--
C3k.3
21726298
13.70
14.34
1.58
0.71
--
C3k.4
21116966
11.94
12.58
1.50
0.68
--
C10k.0
37675440
?
14.93
5.51
2.38
--
C10k.1
37622427
?
14.15
5.08
2.20
--
C10k.2
37338103
?
13.40
5.29
2.29
--
C31k.0
67484350
?
14.05
23.12
7.49
--
C31k.1
67071719
?
13.99
23.30
7.55
--
C100k.0
118913845
?
14.43
100.44
22.60
--
C100k.1
120004848
?
14.66
102.85
23.14
--
C316k.0
213146391
?
14.86
350.53
50.73
--
M1k.0
--
--
--
--
--
--
M1k.1
--
--
--
--
--
--
M1k.2
--
--
--
--
--
--
M1k.3
--
--
--
--
--
--
M3k.0
--
--
--
--
--
--
M3k.1
--
--
--
--
--
--
M10k.0
--
--
--
--
--
--
dsj1000
20776717
11.34
12.02
0.39
0.16
--
pr1002
293925
13.46
14.47
0.39
0.16
--
si1032
--
--
--
--
--
--
u1060
--
--
--
--
--
--
vm1084
--
--
--
--
--
--
pcb1173
66310
16.55
17.67
0.46
0.19
--
d1291
--
--
--
--
--
--
rl1304
302295
19.51
21.36
0.51
0.21
--
rl1323
325854
20.60
22.59
0.52
0.22
--
nrw1379
63391
11.92
12.40
0.56
0.24
--
fl1400
--
--
--
--
--
--
u1432
174112
13.82
14.15
0.62
0.26
--
fl1577
--
--
--
--
--
--
d1655
--
--
--
--
--
--
vm1748
--
--
--
--
--
--
u1817
--
--
--
--
--
--
rl1889
374435
18.29
20.12
0.76
0.33
--
d2103
--
--
--
--
--
--
u2152
--
--
--
--
--
--
u2319
252143
7.64
7.65
1.00
0.44
--
pr2392
440108
16.42
17.84
1.01
0.44
--
pcb3038
158710
15.26
16.20
1.35
0.61
--
fl3795
--
--
--
--
--
--
fnl4461
205734
12.69
13.31
1.90
0.85
--
rl5915
693761
22.67
24.59
2.79
1.24
--
rl5934
670881
20.65
22.32
2.84
1.26
--
pla7397
26938307
15.81
16.48
3.79
1.67
--
rl11849
--
--
--
--
--
--
usa13509
--
--
--
--
--
--
brd14051
531561
13.25
13.79
7.65
3.15
--
d15112
1776620
12.94
13.53
8.30
3.38
--
d18512
731699
13.40
13.95
9.95
3.88
--
pla33810
77620722
17.52
18.13
22.69
7.28
--
pla85900
164891229
15.81
16.28
81.03
19.89
--