ALGORITHM: Convex-Hull-Cheapest-Insertion (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
27077401
15.91
16.80
0.16
0.07
--
E1k.1
26629300
15.85
16.59
0.16
0.07
--
E1k.2
26932574
16.98
17.82
0.17
0.07
--
E1k.3
26773130
15.68
16.39
0.16
0.07
--
E1k.4
26606415
17.22
18.03
0.17
0.07
--
E1k.5
26828033
15.68
16.35
0.16
0.07
--
E1k.6
26913427
15.26
16.17
0.16
0.07
--
E1k.7
26956555
17.82
18.93
0.16
0.07
--
E1k.8
26740969
16.14
17.31
0.16
0.07
--
E1k.9
27430130
17.44
18.16
0.17
0.07
--
E3k.0
48062048
18.28
19.12
0.57
0.26
--
E3k.1
48087215
19.28
20.08
0.55
0.25
--
E3k.2
48041863
19.20
20.09
0.56
0.25
--
E3k.3
48474618
19.43
20.23
0.53
0.24
--
E3k.4
48641487
19.34
20.21
0.55
0.25
--
E10k.0
86334181
?
20.98
1.96
0.85
--
E10k.1
86398311
?
20.73
1.87
0.81
--
E10k.2
85972263
?
20.49
1.94
0.84
--
E31k.0
153578741
?
21.43
7.34
2.38
--
E31k.1
153468221
?
21.18
7.11
2.30
--
E100k.0
272526927
?
21.48
28.36
6.38
--
E100k.1
272663311
?
21.59
29.11
6.55
--
E316k.0
485422470
?
21.79
390.14
56.47
--
E1M.0
864246932
?
21.95
1356.67
248.72
--
E3M.0
1536919363
?
21.98
7619.90
1487.91
--
E10M.0
2732980840
?
22.01
20554.85
4481.63
--
C1k.0
12841405
12.77
13.38
0.21
0.09
--
C1k.1
13045792
14.67
15.14
0.21
0.09
--
C1k.2
12492118
15.08
15.57
0.22
0.09
--
C1k.3
13859747
16.60
17.22
0.22
0.09
--
C1k.4
13354845
16.13
16.80
0.23
0.10
--
C1k.5
12977755
13.89
14.56
0.22
0.09
--
C1k.6
11805040
16.11
16.97
0.23
0.10
--
C1k.7
12719436
19.27
19.96
0.26
0.11
--
C1k.8
13438737
15.79
16.19
0.26
0.11
--
C1k.9
12820014
17.54
18.31
0.22
0.09
--
C3k.0
23118669
20.42
21.16
1.11
0.50
--
C3k.1
22942920
20.64
21.38
1.13
0.51
--
C3k.2
23172916
18.55
19.38
1.13
0.51
--
C3k.3
22844355
19.55
20.23
1.06
0.48
--
C3k.4
22599453
19.80
20.48
1.21
0.55
--
C10k.0
40092977
?
22.30
4.74
2.05
--
C10k.1
40568587
?
23.09
4.02
1.74
--
C10k.2
40451871
?
22.85
4.89
2.11
--
C31k.0
72756182
?
22.96
21.57
6.99
--
C31k.1
72622463
?
23.42
21.17
6.86
--
C100k.0
128511079
?
23.67
82.88
18.65
--
C100k.1
129120395
?
23.37
77.41
17.42
--
C316k.0
230169469
?
24.03
905.06
131.00
--
M1k.0
--
--
--
--
--
--
M1k.1
--
--
--
--
--
--
M1k.2
--
--
--
--
--
--
M1k.3
--
--
--
--
--
--
M3k.0
--
--
--
--
--
--
M3k.1
--
--
--
--
--
--
M10k.0
--
--
--
--
--
--
dsj1000
21902039
17.37
18.09
0.19
0.08
--
pr1002
295940
14.24
15.26
0.16
0.07
--
si1032
--
--
--
--
--
--
u1060
--
--
--
--
--
--
vm1084
--
--
--
--
--
--
pcb1173
67059
17.87
19.00
0.21
0.09
--
d1291
--
--
--
--
--
--
rl1304
302853
19.73
21.58
0.25
0.10
--
rl1323
323994
19.91
21.89
0.24
0.10
--
nrw1379
64949
14.67
15.17
0.22
0.09
--
fl1400
--
--
--
--
--
--
u1432
175478
14.71
15.04
0.25
0.11
--
fl1577
--
--
--
--
--
--
d1655
--
--
--
--
--
--
vm1748
--
--
--
--
--
--
u1817
--
--
--
--
--
--
rl1889
375611
18.66
20.50
0.40
0.17
--
d2103
--
--
--
--
--
--
u2152
--
--
--
--
--
--
u2319
264761
13.02
13.04
0.34
0.15
--
pr2392
443643
17.36
18.78
0.47
0.21
--
pcb3038
160597
16.63
17.58
0.72
0.32
--
fl3795
--
--
--
--
--
--
fnl4461
210889
15.51
16.15
0.83
0.37
--
rl5915
674744
19.31
21.17
1.95
0.87
--
rl5934
669890
20.47
22.14
2.12
0.94
--
pla7397
27948171
20.15
20.85
2.56
1.13
--
rl11849
--
--
--
--
--
--
usa13509
--
--
--
--
--
--
brd14051
552920
17.80
18.37
3.09
1.27
--
d15112
1845394
17.31
17.93
3.39
1.38
--
d18512
757611
17.42
17.99
3.92
1.53
--
pla33810
77418002
17.21
17.83
10.48
3.36
--
pla85900
169394566
18.99
19.45
28.23
6.93
--