2008/10/01 by Deeparnab Chakrabarty, Gagan Goel · 2 citations
Decision Sciences · Computer Science · #Auction Theory and Applications #Optimization and Search Problems #Complexity and Algorithms in Graphs
paper · doi:10.1109/focs.2008.47
openalex publication_date 2008/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
In this paper we consider the following maximum budgeted allocation (MBA) problem: Given a set of m indivisible items and n agents; each agent i willing to pay bijon item j and with a maximum budget of Bi, the goal is to allocate items to agents to maximize revenue. The problem naturally arises as auctioneer revenue maximization in budget-constrained auctions and as winner determination problem in combinatorial auctions when utilities of agents are budgeted-additive.We give a 3/4-approximation algorithm for MBA improving upon the previous best of sime0.632[2, 10]. Our techniques are based on a natural LP relaxation of MBA and our factor is optimal in the sense that it matches the integrality gap of the LP.We prove it is NP-hard to approximate MBA to any factor better than 15/16, previously only NP-hardness was known [21, 17]. Our result also implies NP- hardness of approximating maximum submodular welfare with demand oracle to a factor better than 15/16, improving upon the best known hardness of 275/276[10].Our hardness techniques can be modified to prove that it is NP-hard to approximate the Generalized Assignment Problem (GAP) to any factor better than 10/11. This improves upon the 422/423 hardness of [7, 9].We use iterative rounding on a natural LP relaxation of MBA to obtain the 3/4-approximation. We also give a (3/4 - epsiv) -factor algorithm based on the primal-dual schema which runs in O(nm) time, for any constant epsiv > 0.