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

In this paper we consider the following maximum budgeted allocation (MBA) problem: Given a set of $m$ indivisible items and $n$ agents, with each agent $i$ willing to pay $b_{ij}$ on item $j$ and with a maximum budget of $B_i$, 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 the winner determination problem in combinatorial auctions when utilities of agents are budgeted-additive. Our main results are as follows: (i) We give a $3/4$-approximation algorithm for MBA improving upon the previous best of $\simeq0.632$ [N. Andelman and Y. Mansour, Proceedings of the 9th Scandinavian Workshop on Algorithm Theory (SWAT), 2004, pp. 26-38], [J. Vondrák, Proceedings of the 40th Annual ACM Symposium on the Theory of Computing (STOC), 2008, pp. 67-74] (also implied by the result of [U. Feige and J. Vondrák, Proceedings of the 47th IEEE Symposium on Foundations of Computer Science (FOCS), 2006, pp. 667-676]). 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. (ii) We prove it is NP-hard to approximate MBA to any factor better than $15/16$; previously only NP-hardness was known [T. Sandholm and S. Suri, Games Econom. Behav., 55 (2006), pp. 321-330], [B. Lehmann, D. Lehmann, and N. Nisan, Proceedings of the 3rd ACM Conference on Electronic Commerce (EC), 2001, pp. 18-28]. 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$ [U. Feige and J. Vondrák, Proceedings of the 47th IEEE Symposium on Foundations of Computer Science (FOCS), 2006, pp. 667-676]. (iii) 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 [C. Chekuri and S. Khanna, Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2000, pp. 213-222], [M. Chlebík and J. Chlebíková, Proceedings of the 8th Scandinavian Workshop on Algorithm Theory (SWAT), 2002, pp. 170-179]. We use iterative rounding on a natural LP relaxation of the MBA problem to obtain the $3/4$-approximation. We also give a $(3/4-\epsilon)$-factor algorithm based on the primal-dual schema which runs in $\tilde{O}(nm)$ time, for any constant $\epsilon>0$.