ALGORITHM: Karp-Partitioning:Size=15 (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
31717271
35.77
36.81
0.05
0.02
--
E1k.1
31197480
35.73
36.59
0.05
0.02
--
E1k.2
31333813
36.10
37.08
0.05
0.02
--
E1k.3
31502610
36.12
36.96
0.05
0.02
--
E1k.4
31351345
38.12
39.07
0.05
0.02
--
E1k.5
31224741
34.63
35.42
0.05
0.02
--
E1k.6
31482487
34.83
35.90
0.05
0.02
--
E1k.7
30771548
34.50
35.76
0.05
0.02
--
E1k.8
31442172
36.55
37.93
0.05
0.02
--
E1k.9
31733564
35.87
36.69
0.05
0.02
--
E3k.0
50613620
24.56
25.44
3.90
1.76
--
E3k.1
50086148
24.24
25.07
3.93
1.77
--
E3k.2
50010343
24.08
25.01
3.99
1.80
--
E3k.3
50035891
23.27
24.10
4.00
1.81
--
E3k.4
50919368
24.93
25.84
3.95
1.78
--
E10k.0
92576580
?
29.73
1.82
0.79
--
E10k.1
92434044
?
29.16
1.80
0.78
--
E10k.2
92136168
?
29.13
1.81
0.78
--
E31k.0
169668648
?
34.15
1.60
0.52
--
E31k.1
168843734
?
33.32
1.68
0.54
--
E100k.0
296247033
?
32.06
113.30
25.49
--
E100k.1
295838776
?
31.93
111.60
25.11
--
E316k.0
542732651
?
36.17
60.39
8.74
--
E1M.0
994539526
?
40.33
78.79
14.44
--
E3M.0
1600951886
?
27.06
3221.26
629.00
--
E10M.0
--
--
--
--
--
--
C1k.0
21794449
91.39
92.43
0.05
0.02
--
C1k.1
20127435
76.92
77.63
0.05
0.02
--
C1k.2
21773992
100.59
101.44
0.05
0.02
--
C1k.3
19882447
67.27
68.15
0.05
0.02
--
C1k.4
17202499
49.59
50.45
0.05
0.02
--
C1k.5
21441549
88.17
89.27
0.05
0.02
--
C1k.6
21449117
110.97
112.52
0.05
0.02
--
C1k.7
17430229
63.44
64.39
0.05
0.02
--
C1k.8
24980529
115.24
115.98
0.05
0.02
--
C1k.9
18965555
73.88
75.02
0.05
0.02
--
C3k.0
31391020
63.51
64.52
3.92
1.77
--
C3k.1
33556130
76.45
77.53
4.04
1.82
--
C3k.2
34337735
75.66
76.90
3.97
1.79
--
C3k.3
35231961
84.38
85.42
3.97
1.79
--
C3k.4
38715039
105.23
106.40
3.96
1.79
--
C10k.0
63486710
?
93.66
1.80
0.78
--
C10k.1
65336882
?
98.24
1.80
0.78
--
C10k.2
65434247
?
98.73
1.86
0.80
--
C31k.0
115847942
?
95.79
1.60
0.52
--
C31k.1
122250295
?
107.77
1.60
0.52
--
C100k.0
198333476
?
90.86
113.66
25.57
--
C100k.1
200918810
?
91.97
113.20
25.47
--
C316k.0
370132491
?
99.45
59.33
8.59
--
M1k.0
--
--
--
--
--
--
M1k.1
--
--
--
--
--
--
M1k.2
--
--
--
--
--
--
M1k.3
--
--
--
--
--
--
M3k.0
--
--
--
--
--
--
M3k.1
--
--
--
--
--
--
M10k.0
--
--
--
--
--
--
dsj1000
28886230
54.80
55.75
0.05
0.02
--
pr1002
368372
42.20
43.47
0.05
0.02
--
si1032
--
--
--
--
--
--
u1060
--
--
--
--
--
--
vm1084
--
--
--
--
--
--
pcb1173
81503
43.26
44.63
0.14
0.06
--
d1291
--
--
--
--
--
--
rl1304
397416
57.11
59.54
0.33
0.14
--
rl1323
418998
55.07
57.63
0.37
0.16
--
nrw1379
69983
23.56
24.09
0.52
0.22
--
fl1400
--
--
--
--
--
--
u1432
192352
25.74
26.10
0.72
0.30
--
fl1577
--
--
--
--
--
--
d1655
--
--
--
--
--
--
vm1748
--
--
--
--
--
--
u1817
--
--
--
--
--
--
rl1889
564431
78.31
81.08
0.07
0.03
--
d2103
--
--
--
--
--
--
u2152
--
--
--
--
--
--
u2319
256868
9.65
9.67
0.25
0.11
--
pr2392
521037
37.83
39.51
0.33
0.14
--
pcb3038
169497
23.10
24.09
2.49
1.12
--
fl3795
--
--
--
--
--
--
fnl4461
260437
42.65
43.44
0.40
0.18
--
rl5915
875952
54.89
57.31
4.10
1.82
--
rl5934
862925
55.19
57.33
4.18
1.86
--
pla7397
51197848
120.10
121.38
0.27
0.12
--
rl11849
--
--
--
--
--
--
usa13509
--
--
--
--
--
--
brd14051
646343
37.70
38.37
62.40
25.72
--
d15112
2504891
59.23
60.07
0.64
0.26
--
d18512
940274
45.73
46.43
2.04
0.80
--
pla33810
110384430
67.13
68.00
2.31
0.74
--
pla85900
221992787
55.94
56.55
27.67
6.79
--