ALGORITHM: Karp-Partitioning:Size=20 (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
28123511
20.39
21.31
30.49
12.62
--
E1k.1
27692914
20.48
21.25
30.35
12.56
--
E1k.2
27818830
20.83
21.70
30.09
12.45
--
E1k.3
28092587
21.38
22.13
30.27
12.53
--
E1k.4
27230546
19.97
20.79
30.16
12.48
--
E1k.5
27895007
20.28
20.98
30.25
12.52
--
E1k.6
27987697
19.86
20.81
30.20
12.50
--
E1k.7
27496066
20.18
21.31
30.18
12.49
--
E1k.8
27439723
19.17
20.37
30.52
12.63
--
E1k.9
28099696
20.31
21.04
30.22
12.50
--
E3k.0
50613620
24.56
25.44
4.61
2.08
--
E3k.1
50086148
24.24
25.07
4.69
2.12
--
E3k.2
50010343
24.08
25.01
4.65
2.10
--
E3k.3
50035891
23.27
24.10
4.65
2.10
--
E3k.4
50919368
24.93
25.84
4.78
2.16
--
E10k.0
92576580
?
29.73
1.93
0.83
--
E10k.1
92434044
?
29.16
1.96
0.85
--
E10k.2
92136168
?
29.13
1.99
0.86
--
E31k.0
161490656
?
27.69
842.44
272.90
--
E31k.1
161277592
?
27.34
834.74
270.41
--
E100k.0
296247033
?
32.06
125.72
28.29
--
E100k.1
295838776
?
31.93
127.01
28.58
--
E316k.0
542732651
?
36.11
69.85
10.11
--
E1M.0
880015765
?
24.17
22353.17
4098.08
--
E3M.0
1600951886
?
27.06
3413.33
666.51
--
E10M.0
--
--
--
--
--
--
C1k.0
17786640
56.20
57.04
31.86
13.18
--
C1k.1
17291050
51.99
52.60
31.35
12.97
--
C1k.2
18323185
68.80
69.52
31.62
13.08
--
C1k.3
17871360
50.35
51.15
31.91
13.20
--
C1k.4
15789126
37.30
38.09
31.69
13.11
--
C1k.5
17139985
50.42
51.30
32.09
13.28
--
C1k.6
16262437
59.96
61.13
32.17
13.31
--
C1k.7
14861064
39.35
40.16
31.75
13.14
--
C1k.8
21744633
87.36
88.00
32.10
13.28
--
C1k.9
16568019
51.90
52.90
31.70
13.12
--
C3k.0
31391020
63.51
64.52
4.76
2.15
--
C3k.1
33556130
76.45
77.53
4.90
2.21
--
C3k.2
34337735
75.66
76.90
4.70
2.12
--
C3k.3
35231961
84.38
85.42
4.79
2.16
--
C3k.4
38715039
105.23
106.40
4.71
2.13
--
C10k.0
63486710
?
93.66
2.15
0.93
--
C10k.1
65336882
?
98.24
1.98
0.86
--
C10k.2
65434247
?
98.73
1.95
0.84
--
C31k.0
106313493
?
79.68
871.73
282.39
--
C31k.1
111753211
?
89.93
873.74
283.04
--
C100k.0
198333476
?
90.86
127.80
28.75
--
C100k.1
200918810
?
91.97
129.92
29.23
--
C316k.0
370132491
?
99.45
69.05
9.99
--
M1k.0
--
--
--
--
--
--
M1k.1
--
--
--
--
--
--
M1k.2
--
--
--
--
--
--
M1k.3
--
--
--
--
--
--
M3k.0
--
--
--
--
--
--
M3k.1
--
--
--
--
--
--
M10k.0
--
--
--
--
--
--
dsj1000
25174143
34.91
35.73
30.23
12.51
--
pr1002
337874
30.43
31.59
31.12
12.88
--
si1032
--
--
--
--
--
--
u1060
--
--
--
--
--
--
vm1084
--
--
--
--
--
--
pcb1173
65951
15.92
17.04
459.17
191.39
--
d1291
--
--
--
--
--
--
rl1304
397416
57.11
59.54
0.35
0.15
--
rl1323
418998
55.07
57.63
0.42
0.18
--
nrw1379
69983
23.56
24.09
0.58
0.24
--
fl1400
--
--
--
--
--
--
u1432
192352
25.74
26.10
0.78
0.33
--
fl1577
--
--
--
--
--
--
d1655
--
--
--
--
--
--
vm1748
--
--
--
--
--
--
u1817
--
--
--
--
--
--
rl1889
460362
45.44
47.69
25.59
10.99
--
d2103
--
--
--
--
--
--
u2152
--
--
--
--
--
--
u2319
249692
6.59
6.61
740.75
323.61
--
pr2392
505441
33.70
35.33
1253.04
549.01
--
pcb3038
169497
23.10
24.09
2.69
1.21
--
fl3795
--
--
--
--
--
--
fnl4461
216241
18.45
19.10
846.61
379.26
--
rl5915
875952
54.89
57.31
4.23
1.88
--
rl5934
862925
55.19
57.33
4.37
1.94
--
pla7397
43859202
88.55
89.65
89.33
39.28
--
rl11849
--
--
--
--
--
--
usa13509
--
--
--
--
--
--
brd14051
646343
37.70
38.37
84.20
34.70
--
d15112
2061242
31.03
31.72
245.90
100.03
--
d18512
789310
22.33
22.92
7019.89
2735.83
--
pla33810
101748998
54.05
54.86
3426.13
1099.03
--
pla85900
221992787
55.91
56.55
32.45
7.96
--