Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR13-095 | 24th June 2013 14:35

Welfare Maximization and the Supermodular Degree


Authors: Uriel Feige, Rani Izsak
Publication: 24th June 2013 14:38
Downloads: 1003


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 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.

ISSN 1433-8092 | Imprint