On the configuration LP for maximum budgeted allocation

On the configuration LP for maximum budgeted allocation

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 3[over]4, which matches the best...

Full description

Bibliographic Details
Main Authors: Kalaitzis, Christos, Madry, Aleksander, Newman, Alantha, Poláček, Lukáš, Svensson, Ola
Other Authors: Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science
Format: Article
Language:English
Published: Springer Berlin Heidelberg 2016
Online Access:http://hdl.handle.net/1721.1/103103
https://orcid.org/0000-0003-0536-0323

Internet

http://hdl.handle.net/1721.1/103103
https://orcid.org/0000-0003-0536-0323

Similar Items