ALGORITHM: Nearest-Neighbor:Bentley 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
29514887
26.34
27.31
0.06
0.02
--
E1k.1
28242949
22.87
23.66
0.06
0.02
--
E1k.2
28696733
24.64
25.54
0.07
0.03
--
E1k.3
28705421
24.03
24.80
0.07
0.03
--
E1k.4
28661268
26.27
27.14
0.06
0.02
--
E1k.5
30315440
30.71
31.48
0.07
0.03
--
E1k.6
29221195
25.15
26.13
0.06
0.02
--
E1k.7
29576308
29.27
30.48
0.07
0.03
--
E1k.8
28208696
22.51
23.75
0.06
0.02
--
E1k.9
29201934
25.03
25.79
0.06
0.02
--
E3k.0
51111378
25.78
26.68
0.23
0.10
--
E3k.1
51333861
27.33
28.19
0.23
0.10
--
E3k.2
49842201
23.67
24.59
0.23
0.10
--
E3k.3
50905968
25.42
26.26
0.22
0.10
--
E3k.4
51756346
26.99
27.91
0.23
0.10
--
E10k.0
89314590
?
25.16
0.72
0.31
--
E10k.1
89070831
?
24.46
0.73
0.32
--
E10k.2
89010726
?
24.75
0.73
0.32
--
E31k.0
156685559
?
23.89
2.51
0.81
--
E31k.1
157480280
?
24.35
2.57
0.83
--
E100k.0
276391528
?
23.21
9.10
2.05
--
E100k.1
277748143
?
23.86
10.14
2.28
--
E316k.0
492485361
?
23.56
35.44
5.13
--
E1M.0
874204344
?
23.35
139.29
25.54
--
E3M.0
1549804260
?
23.00
516.53
100.86
--
E10M.0
2754583510
?
22.97
1836.35
400.38
--
C1k.0
14802408
29.99
30.70
0.06
0.02
--
C1k.1
14166621
24.52
25.03
0.06
0.02
--
C1k.2
14148760
30.34
30.90
0.06
0.02
--
C1k.3
15312594
28.82
29.51
0.06
0.02
--
C1k.4
14946280
29.97
30.72
0.07
0.03
--
C1k.5
14359851
26.02
26.76
0.06
0.02
--
C1k.6
13195222
29.79
30.74
0.07
0.03
--
C1k.7
14076695
31.99
32.76
0.07
0.03
--
C1k.8
14972060
29.01
29.45
0.06
0.02
--
C1k.9
14161183
29.84
30.69
0.06
0.02
--
C3k.0
24402718
27.11
27.89
0.22
0.10
--
C3k.1
25389612
33.50
34.33
0.23
0.10
--
C3k.2
25314111
29.50
30.41
0.23
0.10
--
C3k.3
24535324
28.40
29.13
0.23
0.10
--
C3k.4
25216619
33.68
34.43
0.23
0.10
--
C10k.0
42871635
?
30.78
0.71
0.31
--
C10k.1
42204675
?
28.05
0.73
0.32
--
C10k.2
43184155
?
31.15
0.71
0.31
--
C31k.0
77220961
?
30.51
2.49
0.81
--
C31k.1
77867570
?
32.34
2.50
0.81
--
C100k.0
136927290
?
31.77
9.09
2.05
--
C100k.1
136676356
?
30.59
9.08
2.04
--
C316k.0
244583458
?
31.80
35.19
5.09
--
M1k.0
--
--
--
--
--
--
M1k.1
--
--
--
--
--
--
M1k.2
--
--
--
--
--
--
M1k.3
--
--
--
--
--
--
M3k.0
--
--
--
--
--
--
M3k.1
--
--
--
--
--
--
M10k.0
--
--
--
--
--
--
dsj1000
24630468
31.99
32.80
0.06
0.02
--
pr1002
332679
28.43
29.57
0.06
0.02
--
si1032
--
--
--
--
--
--
u1060
--
--
--
--
--
--
vm1084
--
--
--
--
--
--
pcb1173
69752
22.60
23.78
0.08
0.03
--
d1291
--
--
--
--
--
--
rl1304
322877
27.65
29.62
0.08
0.03
--
rl1323
329360
21.90
23.91
0.08
0.03
--
nrw1379
69984
23.56
24.09
0.09
0.04
--
fl1400
--
--
--
--
--
--
u1432
194656
27.25
27.61
0.11
0.05
--
fl1577
--
--
--
--
--
--
d1655
--
--
--
--
--
--
vm1748
--
--
--
--
--
--
u1817
--
--
--
--
--
--
rl1889
388840
22.84
24.75
0.13
0.06
--
d2103
--
--
--
--
--
--
u2152
--
--
--
--
--
--
u2319
281024
19.96
19.99
0.16
0.07
--
pr2392
489744
29.55
31.13
0.16
0.07
--
pcb3038
174219
26.53
27.55
0.22
0.10
--
fl3795
--
--
--
--
--
--
fnl4461
231585
26.85
27.55
0.31
0.14
--
rl5915
685068
21.14
23.03
0.43
0.19
--
rl5934
679674
22.23
23.92
0.48
0.21
--
pla7397
29574686
27.14
27.88
0.56
0.25
--
rl11849
--
--
--
--
--
--
usa13509
--
--
--
--
--
--
brd14051
584403
24.51
25.11
1.09
0.45
--
d15112
1948038
23.84
24.48
1.21
0.49
--
d18512
791744
22.71
23.30
1.39
0.54
--
pla33810
82042547
24.21
24.86
2.78
0.89
--
pla85900
175446897
23.24
23.72
7.86
1.93
--