ALGORITHM: Fast-Recursive-Partitioning - 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
36422864
55.92
57.11
0.03
0.01
--
E1k.1
35693159
55.28
56.28
0.03
0.01
--
E1k.2
34795886
51.13
52.22
0.03
0.01
--
E1k.3
35438944
53.13
54.07
0.03
0.01
--
E1k.4
34791802
53.28
54.34
0.03
0.01
--
E1k.5
35345444
52.40
53.29
0.03
0.01
--
E1k.6
35029142
50.02
51.21
0.03
0.01
--
E1k.7
33430079
46.12
47.48
0.03
0.01
--
E1k.8
34446058
49.60
51.11
0.03
0.01
--
E1k.9
35240424
50.88
51.80
0.03
0.01
--
E3k.0
63050650
55.17
56.27
0.09
0.04
--
E3k.1
61992298
53.77
54.80
0.09
0.04
--
E3k.2
63228518
56.88
58.05
0.09
0.04
--
E3k.3
62587596
54.20
55.23
0.09
0.04
--
E3k.4
61661840
51.29
52.39
0.09
0.04
--
E10k.0
111568410
?
56.34
0.28
0.12
--
E10k.1
110978904
?
55.07
0.28
0.12
--
E10k.2
110938563
?
55.48
0.28
0.12
--
E31k.0
200183438
?
58.28
0.91
0.29
--
E31k.1
196241792
?
54.95
0.91
0.29
--
E100k.0
350215401
?
56.12
3.02
0.68
--
E100k.1
351262625
?
56.64
3.02
0.68
--
E316k.0
623996841
?
56.48
11.02
1.59
--
E1M.0
1110184020
?
56.65
39.66
7.27
--
E3M.0
1974353180
?
56.69
137.48
26.85
--
E10M.0
3512222830
?
56.80
471.58
102.82
--
C1k.0
17003645
49.32
50.13
0.03
0.01
--
C1k.1
20035317
76.11
76.82
0.03
0.01
--
C1k.2
17047646
57.05
57.71
0.03
0.01
--
C1k.3
18793112
58.11
58.94
0.03
0.01
--
C1k.4
17710906
54.01
54.90
0.03
0.01
--
C1k.5
17740282
55.69
56.60
0.03
0.01
--
C1k.6
16170757
59.06
60.22
0.03
0.01
--
C1k.7
16884609
58.32
59.24
0.03
0.01
--
C1k.8
19584889
68.75
69.33
0.03
0.01
--
C1k.9
17495364
60.40
61.46
0.03
0.01
--
C3k.0
35341481
84.09
85.22
0.09
0.04
--
C3k.1
33283377
75.01
76.09
0.09
0.04
--
C3k.2
34481934
76.40
77.64
0.09
0.04
--
C3k.3
33064953
73.04
74.02
0.09
0.04
--
C3k.4
34481919
82.79
83.83
0.09
0.04
--
C10k.0
59550950
?
81.66
0.28
0.12
--
C10k.1
57311177
?
73.89
0.28
0.12
--
C10k.2
58364142
?
77.25
0.28
0.12
--
C31k.0
104935159
?
77.35
0.91
0.29
--
C31k.1
106352698
?
80.75
0.92
0.30
--
C100k.0
188527030
?
81.42
3.02
0.68
--
C100k.1
189607388
?
81.16
3.02
0.68
--
C316k.0
344855258
?
85.83
11.04
1.60
--
M1k.0
--
--
--
--
--
--
M1k.1
--
--
--
--
--
--
M1k.2
--
--
--
--
--
--
M1k.3
--
--
--
--
--
--
M3k.0
--
--
--
--
--
--
M3k.1
--
--
--
--
--
--
M10k.0
--
--
--
--
--
--
dsj1000
29258637
56.80
57.75
0.03
0.01
--
pr1002
425046
64.08
65.54
0.03
0.01
--
si1032
--
--
--
--
--
--
u1060
--
--
--
--
--
--
vm1084
--
--
--
--
--
--
pcb1173
91670
61.13
62.68
0.03
0.01
--
d1291
--
--
--
--
--
--
rl1304
480826
90.09
93.03
0.04
0.02
--
rl1323
496323
83.69
86.72
0.04
0.02
--
nrw1379
85592
51.12
51.77
0.04
0.02
--
fl1400
--
--
--
--
--
--
u1432
225178
47.20
47.62
0.04
0.02
--
fl1577
--
--
--
--
--
--
d1655
--
--
--
--
--
--
vm1748
--
--
--
--
--
--
u1817
--
--
--
--
--
--
rl1889
589213
86.14
89.03
0.05
0.02
--
d2103
--
--
--
--
--
--
u2152
--
--
--
--
--
--
u2319
318078
35.78
35.81
0.07
0.03
--
pr2392
608752
61.03
62.99
0.07
0.03
--
pcb3038
214400
55.71
56.97
0.08
0.04
--
fl3795
--
--
--
--
--
--
fnl4461
272414
49.21
50.03
0.12
0.05
--
rl5915
1107034
95.75
98.80
0.16
0.07
--
rl5934
1025058
84.35
86.89
0.16
0.07
--
pla7397
39261203
68.79
69.77
0.21
0.09
--
rl11849
--
--
--
--
--
--
usa13509
--
--
--
--
--
--
brd14051
714367
52.19
52.93
0.39
0.16
--
d15112
2348429
49.29
50.07
0.42
0.17
--
d18512
986907
52.95
53.70
0.52
0.20
--
pla33810
115811146
75.34
76.26
0.99
0.32
--
pla85900
235866394
65.66
66.33
2.88
0.71
--