|
| |
|
Best
Known Lower Bound to the Maximum |
| Problem
Set #1 |
| n/d |
10% |
20% |
30% |
40% |
50% |
60% |
70% |
80% |
90% |
100% |
| 20 |
4,135 |
3,104 |
7,880 |
5,750 |
8,925 |
7,457 |
9,665 |
6,394 |
9,915 |
12,982 |
| 30 |
4,547 |
7,132 |
13,735 |
11,163 |
15,134 |
13,260 |
16,103 |
20,770 |
19,270 |
21,141 |
| 40 |
8,753 |
17,334 |
17,319 |
23,558 |
27,005 |
22,140 |
26,249 |
30,775 |
38,519 |
39,014 |
| 50 |
12,037 |
19,161 |
32,079 |
32,929 |
40,101 |
33,969 |
39,198 |
41,483 |
45,641 |
53,462 |
| 60 |
22,333 |
27,828 |
36,547 |
45,747 |
37,740 |
42,266 |
57,386 |
55,636 |
56,640 |
65,808 |
| 70 |
26,276 |
25,438 |
40,669 |
44,012 |
50,521 |
62,571 |
55,667 |
70,494 |
81,555 |
81,186 |
| 80 |
26,647 |
39,337 |
56,301 |
55,133 |
86,562 |
80,746 |
85,984 |
96,508 |
85,055 |
84,109 |
| 90 |
39,631 |
55,622 |
70,663 |
73,690 |
83,672 |
118,152 |
93,554 |
101,924 |
101,581 |
103,821 |
| 100 |
36,544 |
68,109 |
71,697 |
93,205 |
91,954 |
102,816 |
117,522 |
133,363 |
131,785 |
159,436 |
| Problem
Set #2 |
| n/d |
10% |
20% |
30% |
40% |
50% |
60% |
70% |
80% |
90% |
100% |
| 20 |
3,447 |
7,682 |
6,253 |
8,144 |
4,848 |
8,280 |
11,395 |
11,162 |
9,013 |
14,151 |
| 30 |
4,094 |
9,643 |
11,583 |
11,217 |
19,079 |
18,907 |
16,145 |
20,740 |
20,077 |
16,290 |
| 40 |
10,664 |
12,562 |
17,022 |
21,362 |
14,916 |
29,214 |
27,535 |
34,771 |
29,689 |
31,053 |
| 50 |
13,574 |
19,208 |
29,522 |
36,384 |
26,311 |
35,694 |
39,567 |
52,949 |
44,255 |
47,421 |
| 60 |
19,719 |
25,760 |
34,056 |
41,411 |
40,327 |
46,020 |
54,506 |
62,806 |
43,447 |
54,772 |
| 70 |
20,822 |
37,624 |
44,140 |
51,322 |
59,392 |
53,220 |
78,847 |
72,831 |
79,521 |
79,012 |
| 80 |
30,039 |
57,029 |
56,046 |
60,594 |
63,193 |
78,579 |
70,784 |
90,182 |
91,869 |
87,425 |
| 90 |
39,578 |
54,260 |
63,851 |
79,137 |
99,326 |
86,962 |
118,065 |
106,213 |
107,961 |
107,966 |
| 100 |
37,208 |
56,754 |
62,100 |
81,672 |
107,514 |
88,321 |
141,470 |
125,854 |
122,122 |
120,499 |
| Problem
Set #3 |
| n/d |
10% |
20% |
30% |
40% |
50% |
60% |
70% |
80% |
90% |
100% |
| 20 |
2,269 |
6,527 |
3,680 |
8,476 |
12,224 |
6,916 |
10,879 |
9,924 |
10,161 |
14,503 |
| 30 |
8,212 |
8,795 |
11,758 |
17,845 |
16,146 |
18,055 |
17,048 |
16,609 |
20,922 |
18,395 |
| 40 |
10,807 |
13,928 |
17,998 |
22,502 |
20,637 |
19,409 |
29,317 |
28,135 |
31,676 |
40,975 |
| 50 |
14,492 |
15,670 |
27,687 |
32,461 |
37,266 |
35,245 |
42,955 |
47,070 |
45,290 |
51,773 |
| 60 |
14,175 |
29,267 |
29,088 |
38,200 |
33,726 |
43,673 |
53,473 |
57,908 |
61,728 |
58,923 |
| 70 |
24,095 |
39,800 |
41,222 |
54,432 |
62,343 |
72,307 |
50,919 |
77,168 |
76,358 |
90,510 |
| 80 |
26,210 |
41,758 |
47,712 |
48,460 |
83,736 |
79,703 |
77,200 |
76,395 |
83,783 |
104,436 |
| 90 |
36,806 |
49,817 |
60,973 |
86,050 |
82,002 |
101,449 |
104,899 |
95,127 |
85,028 |
92,828 |
| 100 |
47,179 |
49,134 |
63,898 |
97,566 |
101,945 |
106,737 |
94,377 |
140,934 |
132,031 |
161,291 |
| Problem
Set #4 |
| n/d |
10% |
20% |
30% |
40% |
50% |
60% |
70% |
80% |
90% |
100% |
| 20 |
3,054 |
2,541 |
4,376 |
8,836 |
6,159 |
7,780 |
14,651 |
14,791 |
9,897 |
8,170 |
| 30 |
6,897 |
9,814 |
8,832 |
16,369 |
13,583 |
16,166 |
10,441 |
19,912 |
18,241 |
16,065 |
| 40 |
8,549 |
11,909 |
21,122 |
19,297 |
25,504 |
24,155 |
34,152 |
31,230 |
23,597 |
34,324 |
| 50 |
10,868 |
26,272 |
23,686 |
20,687 |
29,276 |
38,968 |
41,342 |
44,621 |
38,545 |
52,864 |
| 60 |
18,340 |
21,962 |
33,151 |
46,650 |
50,304 |
42,621 |
48,196 |
54,195 |
51,463 |
74,196 |
| 70 |
17,766 |
41,024 |
40,130 |
48,559 |
77,360 |
45,534 |
67,964 |
75,024 |
73,116 |
72,111 |
| 80 |
33,395 |
35,156 |
68,085 |
64,961 |
70,729 |
84,992 |
75,514 |
95,177 |
103,574 |
81,198 |
| 90 |
35,931 |
44,139 |
63,390 |
87,955 |
82,026 |
92,639 |
75,073 |
101,678 |
96,128 |
122,162 |
| 100 |
37,153 |
67,265 |
75,665 |
74,947 |
102,404 |
81,268 |
100,852 |
109,566 |
116,459 |
172,487 |
| Problem
Set #5 |
| n/d |
10% |
20% |
30% |
40% |
50% |
60% |
70% |
80% |
90% |
100% |
| 20 |
4,342 |
6,710 |
6,466 |
8,550 |
10,493 |
11,942 |
16,178 |
12,692 |
13,515 |
15,315 |
| 30 |
3,660 |
7,668 |
10,594 |
12,061 |
13,432 |
12,704 |
16,601 |
18,417 |
18,660 |
24,246 |
| 40 |
10,556 |
15,436 |
18,568 |
16,412 |
22,504 |
29,310 |
33,097 |
41,500 |
30,521 |
31,545 |
| 50 |
15,498 |
16,280 |
25,487 |
33,587 |
20,562 |
34,157 |
41,457 |
36,485 |
39,699 |
49,119 |
| 60 |
25,055 |
21,742 |
48,643 |
30,540 |
57,820 |
52,084 |
67,020 |
64,833 |
68,222 |
49,145 |
| 70 |
24,854 |
40,151 |
46,064 |
53,359 |
53,029 |
61,782 |
77,860 |
63,951 |
82,207 |
61,011 |
| 80 |
28,205 |
47,365 |
50,883 |
67,776 |
75,189 |
84,182 |
75,155 |
109,608 |
96,597 |
89,154 |
| 90 |
38,899 |
65,446 |
66,180 |
79,250 |
74,961 |
88,767 |
96,259 |
109,633 |
107,325 |
121,997 |
| 100 |
38,744 |
72,007 |
68,001 |
108,514 |
83,877 |
104,716 |
117,737 |
118,397 |
126,867 |
113,410 |
| Problem
Set #6 |
| n/d |
10% |
20% |
30% |
40% |
50% |
60% |
70% |
80% |
90% |
100% |
| 20 |
4,444 |
4,124 |
5,353 |
6,237 |
5,764 |
10,431 |
13,748 |
11,332 |
10,934 |
11,253 |
| 30 |
4,365 |
8,010 |
10,695 |
12,458 |
15,072 |
23,057 |
20,279 |
14,278 |
19,624 |
29,018 |
| 40 |
10,801 |
12,907 |
16,858 |
22,887 |
22,731 |
20,816 |
29,976 |
29,159 |
31,002 |
32,710 |
| 50 |
15,629 |
20,784 |
24,653 |
35,962 |
41,880 |
34,475 |
41,883 |
38,921 |
38,054 |
35,248 |
| 60 |
20,112 |
32,319 |
31,587 |
39,133 |
39,967 |
47,664 |
54,158 |
62,578 |
59,974 |
67,994 |
| 70 |
24,198 |
31,609 |
38,771 |
| |