(a) (Separation Oracle) Describe separation oracles for the following convex sets. Your oracles should run in...

 

Transcribed Image Text:

(a) (Separation Oracle) Describe separation oracles for the following convex sets. Your oracles should run in linear time, assuming the given oracles run in linear time (so you can make a constant number of black-box calls to the given oracles). i. The ball, {x: ||x|| 1}. Recall that ||x||1 = i |xi|. 1 ii. Any convex set A that we have a projection oracle for. I.e. we have an oracle to compute arg min A ||x - y||2 for any y. = {xy A with ||x - iii. The e-neighborhood, E, of any convex set A: E y2 e}, given a projection oracle for A. (b) (Solving Configuration LP) Given a set function f over m items (like submodu- lar/XOS/subadditive) and prices p : [m] Ro of the m items, a single query to the demand oracle returns maxscm] ((S) jes Pj). Now consider the welfare maximization problem from HW1 where we want to allocate m items to n agents where agent i has a combinatorial valuation fi(S) over subset SC [m] and the goal is to maximize the sum of agent valuations. Prove that the following LP relaxation for this welfare maximization problem can be solved using polynomial number of calls to the demand-oracles for the n agents. (Intuitively, here variable xi,s denotes whether set S of items are allocated to agent i.) max wis fi(S) ie[n] SC[m] st. .s51 ie[n] Sej Vj [m] wis1 SC [m] Xi,S 0 Vi [n] VSC [m], Vi [n]. Consider the dual of this LP which has polynomially many variables but exponentially many constraints. Show that the dual LP can be solved optimally in polynomial time since we have a separation oracle using the agent demand oracles. Finally, solve the primal LP where we only allow those primal variables to be non-zero such that their corresponding dual constraint participated while solving the dual LP, i.e., all other primal variables are set to 0. (a) (Separation Oracle) Describe separation oracles for the following convex sets. Your oracles should run in linear time, assuming the given oracles run in linear time (so you can make a constant number of black-box calls to the given oracles). i. The ball, {x: ||x|| 1}. Recall that ||x||1 = i |xi|. 1 ii. Any convex set A that we have a projection oracle for. I.e. we have an oracle to compute arg min A ||x - y||2 for any y. = {xy A with ||x - iii. The e-neighborhood, E, of any convex set A: E y2 e}, given a projection oracle for A. (b) (Solving Configuration LP) Given a set function f over m items (like submodu- lar/XOS/subadditive) and prices p : [m] Ro of the m items, a single query to the demand oracle returns maxscm] ((S) jes Pj). Now consider the welfare maximization problem from HW1 where we want to allocate m items to n agents where agent i has a combinatorial valuation fi(S) over subset SC [m] and the goal is to maximize the sum of agent valuations. Prove that the following LP relaxation for this welfare maximization problem can be solved using polynomial number of calls to the demand-oracles for the n agents. (Intuitively, here variable xi,s denotes whether set S of items are allocated to agent i.) max wis fi(S) ie[n] SC[m] st. .s51 ie[n] Sej Vj [m] wis1 SC [m] Xi,S 0 Vi [n] VSC [m], Vi [n]. Consider the dual of this LP which has polynomially many variables but exponentially many constraints. Show that the dual LP can be solved optimally in polynomial time since we have a separation oracle using the agent demand oracles. Finally, solve the primal LP where we only allow those primal variables to be non-zero such that their corresponding dual constraint participated while solving the dual LP, i.e., all other primal variables are set to 0.