Computational Complexity - Research Seminar
Mahmoud Fouz: Non-Single Minded Envy Free Profit Maximization
Feb. 19, 2009, 10:15 a.m.
E 1 3, Room 415
We consider the problem of envy-free pricing when customers are interested in more than one set of items and when the number of available copies of each item is limited. We observe that the
framework proposed by Cheung and Swamy (2008) can also be applied to this non-single minded case. Informally speaking, this framework uses an α-approximation for the corresponding social welfare maximization problem to obtain an envy-free solution with approximation ratio at least O(α log cmax). Here, cmax denotes the maximum capacity of any item. We apply the generalized framework to the case when items can be structured as
nodes in a tree and each customer's sets of desired items are paths in the tree. In particular, we give a constant factor randomized approximation algorithm for the corresponding SWM problem that,
combined with the above mentioned framework, yields an O(log cmax)-approximate solution to the associated envy-free pricing problem.