Hi,

I managed to prove that the greedy algorithm indeed outputs a correct result for a demand query, however I'm having trouble proving poly(m) time. In each iteration the algorithm needs to compute v(j|S) for items, and we were taught that computing v(j|S) requires computing a demand query several times. Given at worse case the greedy algorithm needs to compute v(j|S) when |S| = m-1, I realized that computing v(j|S) using the greedy algorithm as demand query oracle will result in infinite recursion, since computation of v(j|S) will require computing demand query over items set S + {j} which is the full item set. How should I proceed?

Thanks,

Eldar