Computer Science/Discrete Mathematics Seminar I

In combinatorial allocation, m items are to be assigned to n players so that their total utility is maximized. This problem has many variants depending on the utility functions involved and possible additional constraints. We consider two variants which have been studied recently: the Submodular Welfare Problem (where utility functions are submodular), and the Generalized Assignment Problem (where utility functions are linear and players have additional capacity constraints). For both of these problems, (1-1/e)-approximation algorithms have been developed recently. It turns out that both problems have a common generalization which admits a (1-1/e)-approximation as well, and this is optimal unless P=NP. However, contrary to previous beliefs, we show that 1-1/e is suboptimal for both of the restricted problems mentioned above. This is joint work with Uriel Feige.