Abstract

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. A simple example is the maximum-weight matching, where each item has a value depending on the player receiving it, and at most 1 item can be allocated to each player. More generally, the utility of a player can be a function of the set of items received, rather than a sum of individual items. Several algorithms have been developed recently which achieve an approximation factor of 1-1/e under certain constraints. This factor appears often in approximation algorithms and in many cases it has been proven optimal unless P=NP (e.g., for the allocation problem with fractionally subadditive utilities). It has been conjectured to be optimal in other cases as well, but we show that this conjecture is false, at least in two cases of interest: with submodular utilities, and with linear utilities and knapsack constraints for each player.



Information: