{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T07:03:00Z","timestamp":1760425380864},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2015,7,4]],"date-time":"2015-07-04T00:00:00Z","timestamp":1435968000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2015,12]]},"DOI":"10.1007\/s10107-015-0928-8","type":"journal-article","created":{"date-parts":[[2015,7,3]],"date-time":"2015-07-03T12:36:30Z","timestamp":1435926990000},"page":"427-462","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["On the configuration LP for maximum budgeted allocation"],"prefix":"10.1007","volume":"154","author":[{"given":"Christos","family":"Kalaitzis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aleksander","family":"Ma\u0327dry","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alantha","family":"Newman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luk\u00e1\u0161","family":"Pol\u00e1\u010dek","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ola","family":"Svensson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,7,4]]},"reference":[{"key":"928_CR1","doi-asserted-by":"crossref","unstructured":"Andelman, N., Mansour, Y.: Auctions with budget constraints. In: SWAT, pp. 26\u201338 (2004)","DOI":"10.1007\/978-3-540-27810-8_4"},{"key":"928_CR2","doi-asserted-by":"crossref","unstructured":"Asadpour, A., Feige, U., Saberi, A.: Santa claus meets hypergraph matchings. In: APPROX-RANDOM, pp. 10\u201320. Springer (2008)","DOI":"10.1007\/978-3-540-85363-3_2"},{"key":"928_CR3","first-page":"186","volume":"1","author":"Y Azar","year":"2008","unstructured":"Azar, Y., Birnbaum, B.E., Karlin, A.R., Mathieu, C., Nguyen, C.T.: Improved approximation algorithms for budgeted allocations. ICALP 1, 186\u2013197 (2008)","journal-title":"ICALP"},{"key":"928_CR4","doi-asserted-by":"crossref","unstructured":"Bansal, N., Sviridenko, M.: The santa claus problem. In: Kleinberg, J.M. (ed.) STOC, pp. 31\u201340. ACM (2006)","DOI":"10.1145\/1132516.1132522"},{"key":"928_CR5","doi-asserted-by":"crossref","unstructured":"Chakrabarty, D., Chuzhoy, J., Khanna, S.: On allocating goods to maximize fairness. In: 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25\u201327, 2009, Atlanta, Georgia, USA, pp. 107\u2013116 (2009)","DOI":"10.1109\/FOCS.2009.51"},{"issue":"6","key":"928_CR6","doi-asserted-by":"crossref","first-page":"2189","DOI":"10.1137\/080735503","volume":"39","author":"D Chakrabarty","year":"2010","unstructured":"Chakrabarty, D., Goel, G.: On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and gap. SIAM J. Comput. 39(6), 2189\u20132211 (2010)","journal-title":"SIAM J. Comput."},{"key":"928_CR7","unstructured":"Ebenlendr, T., Kr\u010d\u00e1l, M., Sgall, J.: Graph balancing: a special case of scheduling unrelated parallel machines. In: SODA, pp. 483\u2013490. Society for Industrial and Applied Mathematics (2008)"},{"key":"928_CR8","unstructured":"Feige, U.: On allocations that maximize fairness. In: SODA, pp. 287\u2013293. SIAM (2008)"},{"key":"928_CR9","doi-asserted-by":"crossref","unstructured":"Feige, U., Vondr\u00e1k, J.: Approximation algorithms for allocation problems: improving the factor of 1\u20131\/e. In: FOCS, pp. 667\u2013676 (2006)","DOI":"10.1109\/FOCS.2006.14"},{"issue":"3","key":"928_CR10","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1145\/1147954.1147956","volume":"53","author":"R Gandhi","year":"2006","unstructured":"Gandhi, R., Khuller, S., Parthasarathy, S., Srinivasan, A.: Dependent rounding and its applications to approximation algorithms. J. ACM 53(3), 324\u2013360 (2006)","journal-title":"J. ACM"},{"key":"928_CR11","doi-asserted-by":"crossref","unstructured":"Garg, R., Kumar, V., Pandit, V.: Approximation algorithms for budget-constrained auctions. In: APPROX-RANDOM, pp. 102\u2013113. Springer (2001)","DOI":"10.1007\/3-540-44666-4_14"},{"key":"928_CR12","doi-asserted-by":"crossref","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization, Volume 2 of Algorithms and Combinatorics. Springer, Berlin (1993)","DOI":"10.1007\/978-3-642-78240-4"},{"issue":"4","key":"928_CR13","doi-asserted-by":"crossref","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results. J. ACM 48(4), 798\u2013859 (2001)","journal-title":"J. ACM"},{"issue":"2","key":"928_CR14","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1016\/j.geb.2005.02.006","volume":"55","author":"B Lehmann","year":"2006","unstructured":"Lehmann, B., Lehmann, D.J., Nisan, N.: Combinatorial auctions with decreasing marginal utilities. Games Econ. Behav. 55(2), 270\u2013296 (2006)","journal-title":"Games Econ. Behav."},{"key":"928_CR15","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1007\/BF01585745","volume":"46","author":"JK Lenstra","year":"1990","unstructured":"Lenstra, J.K., Shmoys, D.B., Tardos, \u00c9.: Approximation algorithms for scheduling unrelated parallel machines. Math. Program. 46, 259\u2013271 (1990)","journal-title":"Math. Program."},{"issue":"3","key":"928_CR16","doi-asserted-by":"crossref","first-page":"763","DOI":"10.1137\/S0097539795280895","volume":"27","author":"R Raz","year":"1998","unstructured":"Raz, R.: A parallel repetition theorem. SIAM J. Comput. 27(3), 763\u2013803 (1998)","journal-title":"SIAM J. Comput."},{"key":"928_CR17","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1007\/BF01585178","volume":"62","author":"DB Shmoys","year":"1993","unstructured":"Shmoys, D.B., Tardos, \u00c9.: An approximation algorithm for the generalized assignment problem. Math. Program. 62, 461\u2013474 (1993)","journal-title":"Math. Program."},{"key":"928_CR18","doi-asserted-by":"crossref","unstructured":"Srinivasan, A.: Budgeted allocations in the full-information setting. In: APPROX-RANDOM, pp. 247\u2013253 (2008)","DOI":"10.1007\/978-3-540-85363-3_20"},{"issue":"5","key":"928_CR19","doi-asserted-by":"crossref","first-page":"1318","DOI":"10.1137\/110851201","volume":"41","author":"O Svensson","year":"2012","unstructured":"Svensson, O.: Santa claus schedules jobs on unrelated machines. SIAM J. Comput. 41(5), 1318\u20131341 (2012)","journal-title":"SIAM J. Comput."},{"key":"928_CR20","doi-asserted-by":"crossref","unstructured":"Trevisan, L.: Non-approximability results for optimization problems on bounded degree instances. In: STOC, pp. 453\u2013461 (2001)","DOI":"10.1145\/380752.380839"},{"issue":"6","key":"928_CR21","doi-asserted-by":"crossref","first-page":"2074","DOI":"10.1137\/S0097539797328847","volume":"29","author":"L Trevisan","year":"2000","unstructured":"Trevisan, L., Sorkin, G.B., Sudan, M., Williamson, D.P.: Gadgets, approximation, and linear programming. SIAM J. Comput. 29(6), 2074\u20132097 (2000)","journal-title":"SIAM J. Comput."},{"key":"928_CR22","doi-asserted-by":"crossref","unstructured":"Verschae, J., Wiese, A.: On the configuration-LP for scheduling on unrelated machines. In: Algorithms-ESA, pp. 530\u2013542. Springer (2011)","DOI":"10.1007\/978-3-642-23719-5_45"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-015-0928-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-015-0928-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-015-0928-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,27]],"date-time":"2019-08-27T19:39:18Z","timestamp":1566934758000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-015-0928-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,7,4]]},"references-count":22,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2015,12]]}},"alternative-id":["928"],"URL":"https:\/\/doi.org\/10.1007\/s10107-015-0928-8","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,7,4]]}}}