Previous Up Next

3  A Decision Problem

Given a cut (A,B) with small side A and quotient cut score q, does any subset A' of A define a cut (A',B') with better score q'.


Note that there there are exponentially many subsets A' to consider.


Previous Up Next