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 maximumweight
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 11/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:
Date:  Saturday, Jan. 6, 2007, 15:0016:30  Place:  Niavaran Bldg., Niavaran Square, Tehran, Iran 
