ALGORITHM: 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
28327318
21.26
22.19
0.18
0.07
--
E1k.1
27691611
20.47
21.24
0.18
0.07
--
E1k.2
27263371
18.42
19.27
0.17
0.07
--
E1k.3
28261392
22.11
22.86
0.18
0.07
--
E1k.4
28420633
25.21
26.07
0.17
0.07
--
E1k.5
27899228
20.29
21.00
0.16
0.07
--
E1k.6
28233020
20.91
21.87
0.18
0.07
--
E1k.7
28153583
23.05
24.21
0.16
0.07
--
E1k.8
27753707
20.53
21.75
0.17
0.07
--
E1k.9
27594923
18.15
18.87
0.17
0.07
--
E3k.0
49197243
21.07
21.93
0.63
0.28
--
E3k.1
49519007
22.83
23.66
0.55
0.25
--
E3k.2
49170868
22.00
22.91
0.55
0.25
--
E3k.3
48928257
20.54
21.35
0.62
0.28
--
E3k.4
49465898
21.37
22.25
0.61
0.28
--
E10k.0
86973700
?
21.88
2.25
0.97
--
E10k.1
87111657
?
21.72
1.84
0.80
--
E10k.2
87117729
?
22.10
1.73
0.75
--
E31k.0
154645726
?
22.27
6.81
2.21
--
E31k.1
154501402
?
21.99
7.63
2.47
--
E100k.0
273561815
?
21.95
26.08
5.87
--
E100k.1
273871189
?
22.13
24.61
5.54
--
E316k.0
486281812
?
21.95
385.61
55.81
--
E1M.0
865105313
?
22.07
1451.54
266.12
--
E3M.0
1538049610
?
22.07
3752.24
732.69
--
E10M.0
2734153833
?
22.06
13511.54
2945.96
--
C1k.0
13610150
19.52
20.17
0.27
0.11
--
C1k.1
13848222
21.72
22.22
0.36
0.15
--
C1k.2
12860287
18.47
18.98
0.32
0.13
--
C1k.3
14395332
21.11
21.75
0.37
0.15
--
C1k.4
14069679
22.35
23.05
0.39
0.16
--
C1k.5
13683849
20.09
20.79
0.37
0.15
--
C1k.6
12239599
20.39
21.27
0.30
0.12
--
C1k.7
12884149
20.81
21.51
0.42
0.17
--
C1k.8
13914461
19.89
20.30
0.35
0.14
--
C1k.9
12921679
18.47
19.25
0.32
0.13
--
C3k.0
23264216
21.18
21.93
1.33
0.60
--
C3k.1
22973575
20.80
21.54
1.57
0.71
--
C3k.2
24162477
23.61
24.48
1.34
0.61
--
C3k.3
23344871
22.17
22.86
1.60
0.72
--
C3k.4
23083244
22.37
23.06
1.56
0.70
--
C10k.0
40867026
?
24.66
8.84
3.82
--
C10k.1
40664830
?
23.38
5.22
2.26
--
C10k.2
40756114
?
23.78
5.91
2.56
--
C31k.0
73321924
?
23.92
21.03
6.81
--
C31k.1
73309790
?
24.59
21.43
6.94
--
C100k.0
129513261
?
24.63
88.88
20.00
--
C100k.1
130092816
?
24.30
94.13
21.18
--
C316k.0
230963822
?
24.46
993.31
143.77
--
M1k.0
--
--
--
--
--
--
M1k.1
--
--
--
--
--
--
M1k.2
--
--
--
--
--
--
M1k.3
--
--
--
--
--
--
M3k.0
--
--
--
--
--
--
M3k.1
--
--
--
--
--
--
M10k.0
--
--
--
--
--
--
dsj1000
22417195
20.13
20.87
0.32
0.13
--
pr1002
302998
16.97
18.01
0.20
0.08
--
si1032
--
--
--
--
--
--
u1060
--
--
--
--
--
--
vm1084
--
--
--
--
--
--
pcb1173
69058
21.38
22.55
0.20
0.08
--
d1291
--
--
--
--
--
--
rl1304
312529
23.55
25.47
0.28
0.12
--
rl1323
341370
26.34
28.42
0.30
0.13
--
nrw1379
65366
15.41
15.90
0.27
0.11
--
fl1400
--
--
--
--
--
--
u1432
177288
15.90
16.23
0.20
0.08
--
fl1577
--
--
--
--
--
--
d1655
--
--
--
--
--
--
vm1748
--
--
--
--
--
--
u1817
--
--
--
--
--
--
rl1889
381749
20.60
22.47
0.53
0.23
--
d2103
--
--
--
--
--
--
u2152
--
--
--
--
--
--
u2319
269806
15.18
15.20
0.31
0.14
--
pr2392
455979
20.62
22.09
0.50
0.22
--
pcb3038
163298
18.59
19.56
0.53
0.24
--
fl3795
--
--
--
--
--
--
fnl4461
213541
16.97
17.61
0.84
0.38
--
rl5915
690749
22.14
24.05
1.70
0.75
--
rl5934
685530
23.29
24.99
1.95
0.87
--
pla7397
28355484
21.90
22.61
2.20
0.97
--
rl11849
--
--
--
--
--
--
usa13509
--
--
--
--
--
--
brd14051
554534
18.14
18.71
3.82
1.57
--
d15112
1842913
17.15
17.77
3.23
1.31
--
d18512
755577
17.10
17.67
5.51
2.15
--
pla33810
77040247
16.64
17.25
13.81
4.43
--
pla85900
171268129
20.29
20.78
40.87
10.03
--