|
| |
|
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 |
48,011 |
47,383 |
75,836 |
71,592 |
72,304 |
99,157 |
74,569 |
| 80 |
31,961 |
42,520 |
60,586 |
49,704 |
81,427 |
79,224 |
104,533 |
85,833 |
101,428 |
99,655 |
| 90 |
43,817 |
59,711 |
55,978 |
66,127 |
90,709 |
82,860 |
95,798 |
110,329 |
81,200 |
122,828 |
| 100 |
47,667 |
62,907 |
80,193 |
75,962 |
110,432 |
96,699 |
106,064 |
120,609 |
132,136 |
130,630 |
| Problem
Set #7 |
| n/d |
10% |
20% |
30% |
40% |
50% |
60% |
70% |
80% |
90% |
100% |
| 20 |
2,973 |
4,098 |
7,137 |
7,810 |
4,632 |
11,663 |
8,383 |
9,878 |
10,194 |
13,147 |
| 30 |
5,498 |
5,371 |
11,686 |
16,178 |
15,578 |
17,867 |
21,495 |
17,681 |
25,107 |
19,843 |
| 40 |
13,958 |
18,376 |
17,283 |
21,487 |
23,383 |
34,113 |
31,857 |
29,651 |
31,049 |
51,444 |
| 50 |
16,915 |
19,930 |
22,173 |
34,473 |
41,804 |
39,331 |
39,300 |
62,659 |
48,221 |
45,578 |
| 60 |
16,445 |
24,156 |
33,517 |
39,769 |
47,096 |
34,893 |
58,591 |
50,664 |
61,411 |
67,264 |
| 70 |
25,770 |
29,838 |
53,884 |
49,648 |
50,102 |
90,474 |
50,123 |
64,552 |
98,189 |
91,524 |
| 80 |
24,520 |
48,733 |
48,253 |
52,584 |
71,364 |
85,069 |
87,055 |
77,789 |
95,770 |
91,359 |
| 90 |
30,797 |
53,165 |
50,641 |
72,733 |
121,579 |
91,907 |
89,390 |
90,240 |
94,048 |
97,537 |
| 100 |
45,969 |
66,521 |
76,005 |
87,168 |
104,233 |
128,824 |
113,642 |
117,057 |
132,983 |
136,959 |
| Problem
Set #8 |
| n/d |
10% |
20% |
30% |
40% |
50% |
60% |
70% |
80% |
90% |
100% |
| 20 |
2,434 |
3,976 |
4,358 |
7,386 |
7,018 |
7,527 |
8,243 |
10,375 |
11,364 |
9,406 |
| 30 |
9,291 |
7,904 |
12,028 |
12,543 |
20,363 |
16,180 |
16,519 |
20,014 |
16,718 |
20,869 |
| 40 |
6,117 |
13,336 |
15,699 |
17,165 |
18,547 |
26,350 |
29,315 |
20,957 |
24,648 |
31,657 |
| 50 |
18,035 |
29,380 |
21,760 |
23,174 |
35,954 |
35,464 |
39,895 |
37,922 |
40,862 |
35,001 |
| 60 |
15,704 |
26,602 |
34,598 |
41,441 |
42,968 |
41,363 |
70,337 |
50,157 |
58,253 |
67,723 |
| 70 |
19,606 |
32,639 |
44,907 |
42,570 |
52,535 |
64,763 |
72,469 |
78,403 |
83,389 |
74,475 |
| 80 |
26,835 |
40,651 |
54,221 |
67,749 |
70,953 |
80,640 |
82,631 |
96,991 |
103,377 |
109,223 |
| 90 |
41,457 |
48,730 |
62,371 |
85,462 |
81,022 |
91,633 |
114,826 |
100,423 |
107,495 |
164,480 |
| 100 |
42,214 |
59,601 |
67,486 |
90,406 |
84,407 |
114,396 |
145,882 |
126,349 |
138,858 |
156,735 |
| Problem
Set #9 |
| n/d |
10% |
20% |
30% |
40% |
50% |
60% |
70% |
80% |
90% |
100% |
| 20 |
3,188 |
7,301 |
5,183 |
8,248 |
8,800 |
11,985 |
11,098 |
8,583 |
10,100 |
9,734 |
| 30 |
3,581 |
11,664 |
12,384 |
10,801 |
11,159 |
19,854 |
13,613 |
21,654 |
16,514 |
29,932 |
| 40 |
11,991 |
20,354 |
17,178 |
22,676 |
22,835 |
22,955 |
24,114 |
30,876 |
35,490 |
35,168 |
| 50 |
15,241 |
15,495 |
17,370 |
34,850 |
30,758 |
34,422 |
37,056 |
49,929 |
52,823 |
47,551 |
| 60 |
11,627 |
25,184 |
42,446 |
38,798 |
44,748 |
47,255 |
49,709 |
58,299 |
61,263 |
67,098 |
| 70 |
24,433 |
38,050 |
48,949 |
49,098 |
58,413 |
58,291 |
63,586 |
92,337 |
73,250 |
66,040 |
| 80 |
28,168 |
43,416 |
56,941 |
68,934 |
56,976 |
74,964 |
77,810 |
81,276 |
102,407 |
109,407 |
| 90 |
37,788 |
53,242 |
52,783 |
86,426 |
69,794 |
89,276 |
99,454 |
92,360 |
134,664 |
123,193 |
| 100 |
43,305 |
53,178 |
72,923 |
85,469 |
96,775 |
114,274 |
123,481 |
139,402 |
123,782 |
121,849 |
| Problem
Set #10 |
| n/d |
10% |
20% |
30% |
40% |
50% |
60% |
70% |
80% |
90% |
100% |
| 20 |
1,804 |
4,383 |
5,663 |
5,314 |
9,060 |
10,530 |
10,187 |
12,421 |
11,443 |
9,886 |
| 30 |
9,245 |
7,948 |
11,053 |
11,037 |
12,295 |
16,708 |
25,427 |
20,089 |
23,164 |
19,871 |
| 40 |
9,294 |
16,404 |
12,457 |
18,970 |
32,203 |
30,651 |
17,987 |
21,592 |
28,036 |
30,528 |
| 50 |
14,116 |
27,620 |
18,586 |
30,031 |
40,716 |
30,978 |
38,709 |
36,832 |
41,240 |
50,161 |
| 60 |
16,208 |
25,331 |
41,537 |
31,088 |
42,787 |
36,178 |
45,494 |
70,937 |
66,018 |
53,866 |
| 70 |
25,421 |
30,101 |
37,891 |
48,993 |
52,143 |
49,537 |
52,725 |
81,628 |
87,709 |
90,223 |
| 80 |
34,706 |
48,068 |
55,561 |
60,129 |
70,699 |
78,746 |
94,287 |
101,349 |
101,557 |
92,824 |
| 90 |
47,012 |
51,118 |
61,811 |
70,020 |
76,960 |
93,918 |
87,436 |
111,408 |
128,928 |
98,643 |
| 100 |
45,696 |
53,786 |
78,050 |
89,040 |
73,232 |
105,027 |
109,588 |
120,721 |
136,048 |
126,335 |
|