On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP

Abstract

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 b <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">ij</sub> on item j and with a maximum budget of B <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</sub> , 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.