{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,6]],"date-time":"2025-05-06T09:09:06Z","timestamp":1746522546450},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642315930"},{"type":"electronic","value":"9783642315947"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31594-7_61","type":"book-chapter","created":{"date-parts":[[2012,6,22]],"date-time":"2012-06-22T21:20:21Z","timestamp":1340400021000},"page":"726-737","source":"Crossref","is-referenced-by-count":9,"title":["Quasi-polynomial Local Search for Restricted Max-Min Fair Allocation"],"prefix":"10.1007","author":[{"given":"Lukas","family":"Polacek","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ola","family":"Svensson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"61_CR1","doi-asserted-by":"crossref","unstructured":"Asadpour, A., Feige, U., Saberi, A.: Santa claus meets hypergraph matchings. In: Proceedings of the 11th International Workshop and 12th International Workshop on Approximation, Randomization and Combinatorial Optimization, pp. 10\u201320 (2008); see authors\u2019 homepages for the lower bound of 1\/4 instead of the claimed 1\/5 in the conference version","DOI":"10.1007\/978-3-540-85363-3_2"},{"key":"61_CR2","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1145\/1250790.1250808","volume-title":"Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, STOC 2007","author":"A. Asadpour","year":"2007","unstructured":"Asadpour, A., Saberi, A.: An approximation algorithm for max-min fair allocation of indivisible goods. In: Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, STOC 2007, pp. 114\u2013121. ACM, New York (2007)"},{"key":"61_CR3","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/1132516.1132522","volume-title":"Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, STOC 2006","author":"N. Bansal","year":"2006","unstructured":"Bansal, N., Sviridenko, M.: The santa claus problem. In: Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, STOC 2006, pp. 31\u201340. ACM Press, New York (2006)"},{"key":"61_CR4","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1145\/1536414.1536488","volume-title":"Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009","author":"M. Bateni","year":"2009","unstructured":"Bateni, M., Charikar, M., Guruswami, V.: Maxmin allocation via degree lower-bounded arborescences. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, pp. 543\u2013552. ACM, New York (2009)"},{"key":"61_CR5","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1145\/1120680.1120683","volume":"5","author":"I. Bez\u00e1kov\u00e1","year":"2005","unstructured":"Bez\u00e1kov\u00e1, I., Dani, V.: Allocating indivisible goods. SIGecom. Exch.\u00a05, 11\u201318 (2005)","journal-title":"SIGecom. Exch."},{"key":"61_CR6","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1109\/FOCS.2009.51","volume-title":"Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science FOCS 2009","author":"D. Chakrabarty","year":"2009","unstructured":"Chakrabarty, D., Chuzhoy, J., Khanna, S.: On allocating goods to maximize fairness. In: Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science FOCS 2009, pp. 107\u2013116. IEEE Computer Society Press, Washington, DC (2009)"},{"key":"61_CR7","doi-asserted-by":"publisher","first-page":"1064","DOI":"10.1145\/1109557.1109675","volume-title":"Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, SODA 2006","author":"S. Dobzinski","year":"2006","unstructured":"Dobzinski, S., Schapira, M.: An improved approximation algorithm for combinatorial auctions with submodular bidders. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, SODA 2006, pp. 1064\u20131073. ACM, New York (2006)"},{"key":"61_CR8","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1145\/1132516.1132523","volume-title":"Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, STOC 2006","author":"U. Feige","year":"2006","unstructured":"Feige, U.: On maximizing welfare when utility functions are subadditive. In: Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, STOC 2006, pp. 41\u201350. ACM, New York (2006)"},{"key":"61_CR9","first-page":"287","volume-title":"Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008","author":"U. Feige","year":"2008","unstructured":"Feige, U.: On allocations that maximize fairness. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, pp. 287\u2013293. Society for Industrial and Applied Mathematics, Philadelphia (2008)"},{"key":"61_CR10","series-title":"Leibniz International Proceedings in Informatics (LIPIcs)","first-page":"357","volume-title":"IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2008)","author":"U. Feige","year":"2008","unstructured":"Feige, U.: On estimation algorithms vs approximation algorithms. In: Hariharan, R., Mukund, M., Vinay, V. (eds.) IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2008). Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a02, pp. 357\u2013363. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2008)"},{"key":"61_CR11","doi-asserted-by":"crossref","unstructured":"Feige, U., Vondrak, J.: Approximation algorithms for allocation problems: Improving the factor of 1 - 1\/e. In: 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006, pp. 667\u2013676 (October 2006)","DOI":"10.1109\/FOCS.2006.14"},{"key":"61_CR12","doi-asserted-by":"crossref","unstructured":"Haeupler, B., Saha, B., Srinivasan, A.: New constructive aspects of the lovasz local lemma. In: 2010 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 397\u2013406 (October 2010)","DOI":"10.1109\/FOCS.2010.45"},{"key":"61_CR13","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/BF01585745","volume":"46","author":"J.K. Lenstra","year":"1990","unstructured":"Lenstra, J.K., Shmoys, D.B., Tardos, \u00c9.: Approximation algorithms for scheduling unrelated parallel machines. Math. Program.\u00a046, 259\u2013271 (1990)","journal-title":"Math. Program."},{"key":"61_CR14","first-page":"617","volume-title":"Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, STOC 2011","author":"O. Svensson","year":"2011","unstructured":"Svensson, O.: Santa claus schedules jobs on unrelated machines. In: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, STOC 2011, pp. 617\u2013626. ACM, New York (2011)"},{"key":"61_CR15","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1145\/1374376.1374389","volume-title":"Proceedings of the 40th Annual ACM Symposium on Theory of Computing, STOC 2008","author":"J. Vondrak","year":"2008","unstructured":"Vondrak, J.: Optimal approximation for the submodular welfare problem in the value oracle model. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, STOC 2008, pp. 67\u201374. ACM, New York (2008)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31594-7_61.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T12:15:12Z","timestamp":1620130512000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31594-7_61"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642315930","9783642315947"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31594-7_61","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}