  We study the Maximum Budgeted Allocation problem, which is the problem of
assigning indivisible items to players with budget constraints. In its most
general form, an instance of the MBA problem might include many different
prices for the same item among different players, and different budget
constraints for every player. So far, the best approximation algorithms we know
for the MBA problem achieve a $3/4$-approximation ratio, and employ a natural
LP relaxation, called the Assignment-LP. In this paper, we give an algorithm
for MBA, and prove that it achieves a $3/4+c$-approximation ratio, for some
constant $c>0$. This algorithm works by rounding solutions to an LP called the
Configuration-LP, therefore also showing that the Configuration-LP is strictly
stronger than the Assignment-LP (for which we know that the integrality gap is
$3/4$) for the MBA problem.
