{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,20]],"date-time":"2026-09-20T02:08:01Z","timestamp":1789870081235,"version":"4.0.1"},"reference-count":24,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>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\u201338], [J. Vondr\u00e1k, Proceedings of the 40th Annual ACM Symposium on the Theory of Computing (STOC), 2008, pp. 67\u201374] (also implied by the result of [U. Feige and J. Vondr\u00e1k, Proceedings of the 47th IEEE Symposium on Foundations of Computer Science (FOCS), 2006, pp. 667\u2013676]). 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\u2013330], [B. Lehmann, D. Lehmann, and N. Nisan, Proceedings of the 3rd ACM Conference on Electronic Commerce (EC), 2001, pp. 18\u201328]. 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\u00e1k, Proceedings of the 47th IEEE Symposium on Foundations of Computer Science (FOCS), 2006, pp. 667\u2013676]. (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\u2013222], [M. Chleb\u00edk and J. Chleb\u00edkov\u00e1, Proceedings of the 8th Scandinavian Workshop on Algorithm Theory (SWAT), 2002, pp. 170\u2013179]. 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&gt;0$.<\/jats:p>","DOI":"10.1137\/080735503","type":"journal-article","created":{"date-parts":[[2010,3,17]],"date-time":"2010-03-17T18:06:09Z","timestamp":1268849169000},"page":"2189-2211","source":"Crossref","is-referenced-by-count":30,"title":["On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP"],"prefix":"10.1137","volume":"39","author":[{"given":"Deeparnab","family":"Chakrabarty","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gagan","family":"Goel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2010,3,17]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"Y. Azar, B. Birnbaum, A. Karlin, C. Mathieu, and C. Nguyen,\n                      Improved approximation algorithms for budgeted allocations\n                      , in Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP), 2008, pp. 186\u2013197.","DOI":"10.1007\/978-3-540-70575-8_16"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"N. Andelman and Y. Mansour,\n                      Auctions with budget constraints\n                      , in Proceedings of the 9th Scandinavian Workshop on Algorithm Theory (SWAT), 2004, pp. 26\u201338.","DOI":"10.1007\/978-3-540-27810-8_4"},{"key":"R3","unstructured":"N. Andelman,\n                      Online and Strategic Aspects of Network Resource Management Algorithms\n                      , Ph.D. thesis, Tel Aviv University, Tel Aviv, Israel, 2006."},{"key":"R4","doi-asserted-by":"crossref","unstructured":"N. Buchbinder, K. Jain, and S. Naor,\n                      Online primal-dual algorithms for maximizing ad-auctions revenue\n                      , in Proceedings of the 15th Annual European Symposium ESA, 2007, pp. 253\u2013264.","DOI":"10.1007\/978-3-540-75520-3_24"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1111\/1467-937X.00164"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"L. Blumrosen and N. Nisan,\n                      Combinatorial auctions\n                      , in Algorithmic Game Theory, N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani, eds., Cambridge University Press, Cambridge, UK, 2007, pp. 267\u2013299.","DOI":"10.1017\/CBO9780511800481.013"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"M. Chleb\u00edk and J. Chleb\u00edkov\u00e1,\n                      Approximation hardness of the Steiner tree problem on graphs\n                      , in Proceedings of the 8th Scandinavian Workshop on Algorithm Theory (SWAT), 2002, pp. 170\u2013179.","DOI":"10.1007\/3-540-45471-3_18"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"N. Chen, R. Engelberg, C. Nguyen, P. Raghavendra, A. Rudra, and G. Singh,\n                      Improved approximation algorithms for the spanning star forest problem\n                      , in Proceedings of Approximation Algorithms for Combinatorial Optimization, 10th International Workshop (APPROX), 2007, pp. 44\u201358.","DOI":"10.1007\/978-3-540-74208-1_4"},{"key":"R9","unstructured":"C. Chekuri and S. Khanna,\n                      A PTAS for the multiple knapsack problem\n                      , in Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), ACM, New York, SIAM, Philadelphia, 2000, pp. 213\u2013222."},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10033"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"L. Fleischer, M. X. Goemans, V. S. Mirrokni, and M. Sviridenko,\n                      Tight approximation algorithms for maximum general assignment problems\n                      , in Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), ACM, New York, SIAM, Philadelphia, 2006, pp. 611\u2013620.","DOI":"10.1145\/1109557.1109624"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"U. Feige and J. Vondr\u00e1k,\n                      Approximation algorithms for allocation problems: Improving the factor of $1-1\/e$\n                      , in Proceedings of the 47th IEEE Symposium on Foundations of Computer Science (FOCS), 2006, pp. 667\u2013676.","DOI":"10.1109\/FOCS.2006.14"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"R. Garg, V. Kumar, and V. Pandit,\n                      Approximation algorithms for budget-constrained auctions\n                      , in Proceedings of Approximation Algorithms for Combinatorial Optimization, 5th International Workshop (APPROX), 2001, pp. 102\u2013113.","DOI":"10.1007\/3-540-44666-4_14"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"S. Khot, R. Lipton, E. Markakis, and A. Mehta,\n                      Inapproximability results for combinatorial auctions with submodular utility functions\n                      , in Proceedings of the Workshop on Internet and Network Economics (WINE), 2005, pp. 92\u2013101.","DOI":"10.1007\/11600930_10"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"B. Lehmann, D. Lehmann, and N. Nisan,\n                      Combinatorial auctions with decreasing marginal utilities\n                      , in Proceedings of the 3rd ACM Conference on Electronic Commerce (EC), 2001, pp. 18\u201328.","DOI":"10.1145\/501158.501161"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585745"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"A. Mehta, A. Saberi, U. V. Vazirani, and V. V. Vazirani,\n                      Adwords and generalized on-line matching\n                      , J. ACM, 54 (5) (2007), article 22.","DOI":"10.1145\/1284320.1284321"},{"key":"R19","unstructured":"C. T. Nguyen, J. Shen, M. Hou, L. Sheng, W. Miller, and L. Zhang,\n                      Approximating the spanning star forest problem and its applications to genomic sequence alignment\n                      , in Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), ACM, New York, SIAM, Philadelphia, 2007, pp. 645\u2013654."},{"key":"R20","doi-asserted-by":"crossref","unstructured":"A. Srinivasan,\n                      Budgeted allocations in the full-information setting\n                      , in Proceedings of Approximation Algorithms for Combinatorial Optimization, International Workshop (APPROX), 2008, pp. 247\u2013253.","DOI":"10.1007\/978-3-540-85363-3_20"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2005.06.001"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585178"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"V. V. Vazirani,\n                      Approximation Algorithms\n                      , Springer, Berlin, 2002.","DOI":"10.1007\/978-3-662-04565-7"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"J. Vondr\u00e1k,\n                      Optimal approximation for the submodular welfare problem in the value oracle model\n                      , in Proceedings of the 40th Annual ACM Symposium on the Theory of Computing (STOC), 2008, pp. 67\u201374.","DOI":"10.1145\/1374376.1374389"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/080735503","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:36:31Z","timestamp":1787337391000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/080735503"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":24,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/080735503"],"URL":"https:\/\/doi.org\/10.1137\/080735503","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]}}}