New answers tagged

0

The cut you are after is from sB through BA through At. The sB arrow comes from the left to the right. This direction determines the rest of the calculations. Count it as 2. But the BA arrow comes from the right to the left. This is discarded, and counted as zero. The At arrow comes from left to the right. It is counted as 2. Thus the total, and the ...


0

Your problem is essentially Minimum $k$-Union. In this problem (switching from $k$ to $\ell$), you want to find $\ell$ sets out of $A_1,\ldots,A_t$ which together cover the least number of elements. Denoting by $f(\ell)$ the solution of this problem and by $g(j)$ the solution of your problem, we have $$ f(\ell) \leq j \Longleftrightarrow \ell \leq g(j). $$ ...


Top 50 recent answers are included