{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T09:30:19Z","timestamp":1758274219350,"version":"3.41.0"},"reference-count":16,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2015,11,17]],"date-time":"2015-11-17T00:00:00Z","timestamp":1447718400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ERC Starting","award":["335288-OptApprox"],"award-info":[{"award-number":["335288-OptApprox"]}]},{"name":"ERC Advanced investigator","award":["228021 and 226203"],"award-info":[{"award-number":["228021 and 226203"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2016,2,12]]},"abstract":"<jats:p>The restricted max-min fair allocation problem (also known as the restricted Santa Claus problem) is one of few problems that enjoys the intriguing status of having a better estimation algorithm than approximation algorithm. Indeed, Asadpour et al. [2012] proved that a certain configuration LP can be used to estimate the optimal value within a factor of 1\/(4 + \u03f5), for any \u03f5 &gt; 0, but at the same time it is not known how to efficiently find a solution with a comparable performance guarantee.<\/jats:p>\n          <jats:p>\n            A natural question that arises from their work is if the difference between these guarantees is inherent or results from a lack of suitable techniques. We address this problem by giving a quasi-polynomial approximation algorithm with the mentioned performance guarantee. More specifically, we modify the local search of Asadpour et al. [2012] and provide a novel analysis that lets us significantly improve the bound on its running time: from 2\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (\n              <jats:italic>n<\/jats:italic>\n              )\n            <\/jats:sup>\n            to\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (log\n              <jats:italic>n<\/jats:italic>\n              )\n            <\/jats:sup>\n            . Our techniques also have the interesting property that although we use the rather complex configuration LP in the analysis, we never actually solve it and therefore the resulting algorithm is purely combinatorial.\n          <\/jats:p>","DOI":"10.1145\/2818695","type":"journal-article","created":{"date-parts":[[2015,11,18]],"date-time":"2015-11-18T13:42:28Z","timestamp":1447854148000},"page":"1-13","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Quasi-Polynomial Local Search for Restricted Max-Min Fair Allocation"],"prefix":"10.1145","volume":"12","author":[{"given":"Luk\u00e1\u0161","family":"Pol\u00e1\u010dek","sequence":"first","affiliation":[{"name":"KTH Royal Institute of Technology, Stockholm, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ola","family":"Svensson","sequence":"additional","affiliation":[{"name":"EPFL, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,11,17]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722219"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229163.2229168"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250808"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132522"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536488"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1120680.1120683"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/1747597.1748028"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109675"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132523"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908)","author":"Feige Uriel","year":"2008","unstructured":"Uriel Feige . 2008 a. On allocations that maximize fairness . In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908) . Society for Industrial and Applied Mathematics, Philadelphia, PA, 287--293. Uriel Feige. 2008a. On allocations that maximize fairness. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908). Society for Industrial and Applied Mathematics, Philadelphia, PA, 287--293."},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201908)","volume":"2","author":"Feige Uriel","year":"2008","unstructured":"Uriel Feige . 2008 b. On estimation algorithms vs approximation algorithms . In Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201908) (Leibniz International Proceedings in Informatics (LIPIcs)), Ramesh Hariharan, Madhavan Mukund, and V. Vinay (Eds.) , Vol. 2 . Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 357--363. Uriel Feige. 2008b. On estimation algorithms vs approximation algorithms. In Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201908) (Leibniz International Proceedings in Informatics (LIPIcs)), Ramesh Hariharan, Madhavan Mukund, and V. Vinay (Eds.), Vol. 2. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 357--363."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.14"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.45"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585745"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/110851201"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374389"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2818695","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2818695","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:42:49Z","timestamp":1750225369000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2818695"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,11,17]]},"references-count":16,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,2,12]]}},"alternative-id":["10.1145\/2818695"],"URL":"https:\/\/doi.org\/10.1145\/2818695","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2015,11,17]]},"assertion":[{"value":"2014-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-11-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}