# 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 *c*_{max}). Here, *c*_{max} 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 *c*_{max})-approximate solution to the associated envy-free pricing problem.