ALGORITHM: Random-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
26135548
11.88
12.73
0.15
0.06
--
E1k.1
26207513
14.02
14.75
0.14
0.06
--
E1k.2
26118493
13.44
14.26
0.15
0.06
--
E1k.3
26061622
12.61
13.30
0.15
0.06
--
E1k.4
26241580
15.61
16.41
0.14
0.06
--
E1k.5
26309323
13.44
14.10
0.15
0.06
--
E1k.6
26582564
13.84
14.75
0.15
0.06
--
E1k.7
25310136
10.63
11.66
0.15
0.06
--
E1k.8
26047536
13.12
14.27
0.14
0.06
--
E1k.9
26330235
12.73
13.42
0.15
0.06
--
E3k.0
46292271
13.92
14.73
0.52
0.23
--
E3k.1
46036409
14.19
14.96
0.52
0.23
--
E3k.2
46413360
15.16
16.01
0.53
0.24
--
E3k.3
46585874
14.77
15.54
0.52
0.23
--
E3k.4
46528377
14.16
14.99
0.51
0.23
--
E10k.0
81990199
?
14.89
1.64
0.71
--
E10k.1
82248130
?
14.93
1.66
0.72
--
E10k.2
82270678
?
15.30
1.63
0.70
--
E31k.0
146207114
?
15.60
5.97
1.93
--
E31k.1
146130605
?
15.38
6.06
1.96
--
E100k.0
258862154
?
15.39
25.10
5.65
--
E100k.1
258940912
?
15.47
25.29
5.69
--
E316k.0
460032337
?
15.42
90.20
13.06
--
E1M.0
818423431
?
15.48
327.09
59.97
--
E3M.0
1454861570
?
15.47
1135.19
221.66
--
E10M.0
2587131700
?
15.50
3906.77
851.80
--
C1k.0
12578345
10.46
11.06
0.15
0.06
--
C1k.1
12616235
10.90
11.34
0.15
0.06
--
C1k.2
12252896
12.88
13.36
0.15
0.06
--
C1k.3
13174357
10.84
11.42
0.15
0.06
--
C1k.4
12711332
10.53
11.17
0.16
0.07
--
C1k.5
13010750
14.18
14.85
0.14
0.06
--
C1k.6
11869947
16.75
17.61
0.16
0.07
--
C1k.7
11958500
12.13
12.78
0.16
0.07
--
C1k.8
13030346
12.28
12.66
0.16
0.07
--
C1k.9
12157322
11.46
12.19
0.15
0.06
--
C3k.0
21752217
13.30
14.00
0.50
0.23
--
C3k.1
21523947
13.18
13.87
0.51
0.23
--
C3k.2
21920532
12.14
12.93
0.52
0.23
--
C3k.3
21644490
13.27
13.91
0.50
0.23
--
C3k.4
21510205
14.03
14.67
0.50
0.23
--
C10k.0
38018356
?
15.97
1.60
0.69
--
C10k.1
38337832
?
16.32
1.60
0.69
--
C10k.2
38181423
?
15.96
1.59
0.69
--
C31k.0
68483619
?
15.74
5.74
1.86
--
C31k.1
67929738
?
15.45
5.79
1.88
--
C100k.0
120692293
?
16.14
24.46
5.50
--
C100k.1
121720683
?
16.30
24.39
5.49
--
C316k.0
215885811
?
16.33
87.64
12.68
--
M1k.0
--
--
--
--
--
--
M1k.1
--
--
--
--
--
--
M1k.2
--
--
--
--
--
--
M1k.3
--
--
--
--
--
--
M3k.0
--
--
--
--
--
--
M3k.1
--
--
--
--
--
--
M10k.0
--
--
--
--
--
--
dsj1000
21020573
12.65
13.34
0.14
0.06
--
pr1002
295604
14.11
15.13
0.15
0.06
--
si1032
--
--
--
--
--
--
u1060
--
--
--
--
--
--
vm1084
--
--
--
--
--
--
pcb1173
66584
17.04
18.16
0.19
0.08
--
d1291
--
--
--
--
--
--
rl1304
306479
21.16
23.04
0.18
0.08
--
rl1323
323676
19.79
21.77
0.18
0.08
--
nrw1379
64007
13.01
13.50
0.23
0.10
--
fl1400
--
--
--
--
--
--
u1432
173426
13.37
13.70
0.26
0.11
--
fl1577
--
--
--
--
--
--
d1655
--
--
--
--
--
--
vm1748
--
--
--
--
--
--
u1817
--
--
--
--
--
--
rl1889
371881
17.48
19.31
0.27
0.12
--
d2103
--
--
--
--
--
--
u2152
--
--
--
--
--
--
u2319
252417
7.75
7.77
0.47
0.21
--
pr2392
437951
15.85
17.26
0.39
0.17
--
pcb3038
159385
15.75
16.69
0.54
0.24
--
fl3795
--
--
--
--
--
--
fnl4461
208610
14.27
14.89
0.77
0.34
--
rl5915
692567
22.46
24.37
0.91
0.40
--
rl5934
670720
20.62
22.29
0.92
0.41
--
pla7397
27095100
16.48
17.16
1.30
0.57
--
rl11849
--
--
--
--
--
--
usa13509
--
--
--
--
--
--
brd14051
534374
13.85
14.40
2.63
1.08
--
d15112
1788287
13.68
14.28
2.79
1.13
--
d18512
732946
13.59
14.15
3.46
1.35
--
pla33810
78766666
19.25
19.88
6.74
2.16
--
pla85900
166470964
16.94
17.39
22.87
5.61
--