TY - CPAPER
DO - 10.1007/978-3-319-07557-0_28
AB - We study the Maximum Budgeted Allocation problem, i.e., the problem of selling a set of m indivisible goods to n players, each with a separate budget, such that we maximize the collected revenue. Since the natural assignment LP is known to have an integrality gap of, which matches the best known approximation algorithms, our main focus is to improve our understanding of the stronger configuration LP relaxation. In this direction, we prove that the integrality gap of the configuration LP is strictly better than, and provide corresponding polynomial time roundings, in the following restrictions of the problem: (i) the Restricted Budgeted Allocation problem, in which all the players have the same budget and every item has the same value for any player it can be sold to, and (ii) the graph MBA problem, in which an item can be assigned to at most 2 players. Finally, we improve the best known upper bound on the integrality gap for the general case from 5/6 to 2√2 2 ≈ 0.828 and also prove hardness of approximation results for both cases. © 2014 Springer International Publishing Switzerland.
T1 - On the Configuration LP for Maximum Budgeted Allocation
ED - Lee, Jon
ED - Vygen, Jens
DA - 2014
AU - Kalaitzis, Christos
AU - Madry, Aleksander
AU - Newman, Alantha
AU - Polacek, Lukas
AU - Svensson, Ola
JF - Integer Programming and Combinatorial Optimization - 17th International Conference, IPCO 2014, Bonn, Germany, June 23-25, 2014. Proceedings
SP - 333-344
VL - 8494
EP - 333-344
PB - Springer
ID - 228017
SN - 978-3-319-07556-3
ER -