H2 q1

Summary:

Demand query needs marginal values

H2 q1

eldarsehayek 25 May 2018 09:58

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

Re: H2 q1

KineretS 26 May 2018 14:31

I'm not sure that I understand your question. The greedy process takes polynomial time. Do you agree on that?

Re: H2 q1

eldarsehayek 28 May 2018 21:04

The greedy process takes polynomial time only if we can assume value queries are answered in polynomial time. I can't see a way to avoid that, and it's a reasonable assumption given the value function is fixed, so I'll assume that's the case and write it explicitly.