Welfare Maximization and the Supermodular Degree
Event details
| Date | 20.08.2014 |
| Hour | 16:15 › 17:15 |
| Speaker | Rani Izsak, Weizmann Institute |
| Location | |
| Category | Conferences - Seminars |
Given a set of items and a collection of players, each with a nonnegative monotone valuation set function over the items, the welfare maximization problem requires that every item be allocated to exactly one player, and one wishes to maximize the sum of values obtained by the players, as computed by applying the respective valuation function to the bundle of items allocated to the player. This problem in its full generality is $\NP$-hard, and moreover, at least as hard to approximate as set packing. Better approximation guarantees are known for restricted classes of valuation functions. In this work we introduce a new parameter, the {\em supermodular degree} of a valuation function, which is a measure for the extent to which the function exhibits supermodular behavior. We design an approximation algorithm for the welfare maximization problem whose approximation guarantee is linear in the supermodular degree of the underlying valuation functions.
Joint work with Uriel Feige.
Joint work with Uriel Feige.
Practical information
- Informed public
- Free
- This event is internal
Organizer
- Moran Feldman