{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T11:10:25Z","timestamp":1725793825884},"publisher-location":"Cham","reference-count":17,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319075563"},{"type":"electronic","value":"9783319075570"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-07557-0_28","type":"book-chapter","created":{"date-parts":[[2014,5,17]],"date-time":"2014-05-17T11:50:30Z","timestamp":1400327430000},"page":"333-344","source":"Crossref","is-referenced-by-count":0,"title":["On the Configuration LP for Maximum Budgeted Allocation"],"prefix":"10.1007","author":[{"given":"Christos","family":"Kalaitzis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aleksander","family":"M\u0105dry","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","reference":[{"key":"28_CR1","doi-asserted-by":"crossref","unstructured":"Andelman, N., Mansour, Y.: Auctions with budget constraints. In: Hagerup, T., Katajainen, J. (eds.) SWAT 2004. LNCS, vol.\u00a03111, pp. 26\u201338. Springer, Heidelberg (2004)","DOI":"10.1007\/978-3-540-27810-8_4"},{"key":"28_CR2","doi-asserted-by":"crossref","unstructured":"Asadpour, A., Feige, U., Saberi, A.: Santa claus meets hypergraph matchings. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds.) APPROX and RANDOM 2008. LNCS, vol.\u00a05171, pp. 10\u201320. Springer, Heidelberg (2008)","DOI":"10.1007\/978-3-540-85363-3_2"},{"key":"28_CR3","doi-asserted-by":"crossref","unstructured":"Azar, Y., Birnbaum, B.E., Karlin, A.R., Mathieu, C., Nguyen, C.T.: Improved approximation algorithms for budgeted allocations. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol.\u00a05125, pp. 186\u2013197. Springer, Heidelberg (2008)","DOI":"10.1007\/978-3-540-70575-8_16"},{"key":"28_CR4","doi-asserted-by":"crossref","unstructured":"Bansal, N., Sviridenko, M.: The santa claus problem. In: Kleinberg, J.M. (ed.) STOC, pp. 31\u201340. ACM Press (2006)","DOI":"10.1145\/1132516.1132522"},{"key":"28_CR5","doi-asserted-by":"crossref","unstructured":"Chakrabarty, D., Goel, G.: On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and gap. SIAM J. Comput.\u00a039(6), 2189\u20132211 (2010)","DOI":"10.1137\/080735503"},{"key":"28_CR6","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":"28_CR7","unstructured":"Feige, U.: On allocations that maximize fairness. In: SODA, pp. 287\u2013293. SIAM (2008)"},{"key":"28_CR8","doi-asserted-by":"crossref","unstructured":"Feige, U., Vondr\u00e1k, J.: Approximation algorithms for allocation problems: Improving the factor of 1 - 1\/e. In: FOCS, pp. 667\u2013676 (2006)","DOI":"10.1109\/FOCS.2006.14"},{"key":"28_CR9","doi-asserted-by":"crossref","unstructured":"Gandhi, R., Khuller, S., Parthasarathy, S., Srinivasan, A.: Dependent rounding and its applications to approximation algorithms. J. ACM\u00a053(3), 324\u2013360 (2006)","DOI":"10.1145\/1147954.1147956"},{"key":"28_CR10","doi-asserted-by":"crossref","unstructured":"Garg, R., Kumar, V., Pandit, V.: Approximation algorithms for budget-constrained auctions. In: Goemans, M.X., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) RANDOM 2001 and APPROX 2001. LNCS, vol.\u00a02129, pp. 102\u2013113. Springer, Heidelberg (2001)","DOI":"10.1007\/3-540-44666-4_14"},{"key":"28_CR11","doi-asserted-by":"crossref","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Algorithms and Combinatorics, vol.\u00a02. Springer (1993)","DOI":"10.1007\/978-3-642-78240-4"},{"key":"28_CR12","doi-asserted-by":"crossref","unstructured":"Lehmann, B., Lehmann, D.J., Nisan, N.: Combinatorial auctions with decreasing marginal utilities. Games and Economic Behavior\u00a055(2), 270\u2013296 (2006)","DOI":"10.1016\/j.geb.2005.02.006"},{"key":"28_CR13","doi-asserted-by":"crossref","unstructured":"Lenstra, J.K., Shmoys, D.B., Tardos, \u00c9.: Approximation algorithms for scheduling unrelated parallel machines. Math. Program.\u00a046, 259\u2013271 (1990)","DOI":"10.1007\/BF01585745"},{"key":"28_CR14","doi-asserted-by":"crossref","unstructured":"Shmoys, D.B., Tardos, \u00c9.: An approximation algorithm for the generalized assignment problem. Math. Program.\u00a062, 461\u2013474 (1993)","DOI":"10.1007\/BF01585178"},{"key":"28_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/978-3-540-85363-3_20","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"A. Srinivasan","year":"2008","unstructured":"Srinivasan, A.: Budgeted allocations in the full-information setting. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds.) APPROX and RANDOM 2008. LNCS, vol.\u00a05171, pp. 247\u2013253. Springer, Heidelberg (2008)"},{"key":"28_CR16","doi-asserted-by":"crossref","unstructured":"Svensson, O.: Santa claus schedules jobs on unrelated machines. SIAM J. Comput.\u00a041(5), 1318\u20131341 (2012)","DOI":"10.1137\/110851201"},{"key":"28_CR17","doi-asserted-by":"crossref","unstructured":"Verschae, J., Wiese, A.: On the configuration-LP for scheduling on unrelated machines. In: Demetrescu, C., Halld\u00f3rsson, M.M. (eds.) ESA 2011. LNCS, vol.\u00a06942, pp. 530\u2013542. Springer, Heidelberg (2011)","DOI":"10.1007\/978-3-642-23719-5_45"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-07557-0_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,10]],"date-time":"2019-08-10T15:25:07Z","timestamp":1565450707000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-07557-0_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319075563","9783319075570"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-07557-0_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}