{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,25]],"date-time":"2026-01-25T10:25:50Z","timestamp":1769336750756,"version":"3.49.0"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2022,2,23]],"date-time":"2022-02-23T00:00:00Z","timestamp":1645574400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,2,23]],"date-time":"2022-02-23T00:00:00Z","timestamp":1645574400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"name":"Research Grant Council, Hong Kong","award":["16207419"],"award-info":[{"award-number":["16207419"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,7]]},"DOI":"10.1007\/s00453-022-00942-y","type":"journal-article","created":{"date-parts":[[2022,2,23]],"date-time":"2022-02-23T12:03:15Z","timestamp":1645617795000},"page":"1835-1874","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Restricted Max-Min Allocation: Integrality Gap and Approximation Algorithm"],"prefix":"10.1007","volume":"84","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3557-9935","authenticated-orcid":false,"given":"Siu-Wing","family":"Cheng","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1075-344X","authenticated-orcid":false,"given":"Yuchen","family":"Mao","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,2,23]]},"reference":[{"issue":"3","key":"942_CR1","doi-asserted-by":"publisher","first-page":"37:1","DOI":"10.1145\/3070694","volume":"13","author":"C Annamalai","year":"2017","unstructured":"Annamalai, C., Kalaitzis, C., Svensson, O.: Combinatorial algorithm for restricted max-min fair allocation. ACM Trans. Algorithms 13(3), 37:1-37:28 (2017)","journal-title":"ACM Trans. Algorithms"},{"issue":"3","key":"942_CR2","doi-asserted-by":"publisher","first-page":"24:1","DOI":"10.1145\/2229163.2229168","volume":"8","author":"A Asadpour","year":"2012","unstructured":"Asadpour, A., Feige, U., Saberi, A.: Santa Claus meets hypergraph matchings. ACM Trans. Algorithms 8(3), 24:1-24:9 (2012)","journal-title":"ACM Trans. Algorithms"},{"key":"942_CR3","doi-asserted-by":"crossref","unstructured":"Asadpour, A., Saberi, A.: An approximation algorithm for max-min fair allocation of indivisible goods. In: Proceedings of the 39th ACM Symposium on Theory of Computing, pp. 114\u2013121 (2007)","DOI":"10.1145\/1250790.1250808"},{"key":"942_CR4","doi-asserted-by":"crossref","unstructured":"Bansal, N., Sviridenko, M.: The Santa Claus problem. In: Proceedings of the 38th ACM Symposium on Theory of Computing, pp. 31\u201340 (2006)","DOI":"10.1145\/1132516.1132522"},{"key":"942_CR5","doi-asserted-by":"crossref","unstructured":"Bateni, M., Charikar, M., Guruswami, V.: Max-min allocation via degree lower-bounded arborescences. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, pp. 543\u2013552 (2009)","DOI":"10.1145\/1536414.1536488"},{"issue":"3","key":"942_CR6","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 Exchanges 5(3), 11\u201318 (2005)","journal-title":"SIGecom Exchanges"},{"key":"942_CR7","doi-asserted-by":"crossref","unstructured":"Chakrabarty, D., Chuzhoy, J., Khanna, S.: On allocating goods to maximize fairness. In: Proceedings of the 50th IEEE Symposium on Foundations of Computer Science, pp. 107\u2013116 (2009)","DOI":"10.1109\/FOCS.2009.51"},{"key":"942_CR8","unstructured":"Cheng, S., Mao, Y.: Integrality gap of the configuration LP for the restricted max-min fair allocation. CoRR arXiv:1807.04152 (2018)"},{"key":"942_CR9","unstructured":"Cheng, S., Mao, Y.: Restricted max-min fair allocation. In: Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, pp. 37:1\u201337:13 (2018)"},{"key":"942_CR10","unstructured":"Cheng, S., Mao, Y.: Restricted max-min allocation: Approximation and integrality gap. In: Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, pp. 38:1\u201338:13 (2019)"},{"key":"942_CR11","unstructured":"Davies, S., Rothvoss, T., Zhang, Y.: A tale of Santa Claus, hypergraphs and matroids. CoRR arXiv:1807.07189v1 (2018)"},{"key":"942_CR12","doi-asserted-by":"crossref","unstructured":"Davies, S., Rothvoss, T., Zhang, Y.: A tale of Santa Claus, hypergraphs and matroids. In: Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2748\u20132757 (2020)","DOI":"10.1137\/1.9781611975994.167"},{"key":"942_CR13","unstructured":"Feige, U.: On allocations that maximize fairness. In: Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms, pp. 287\u2013293 (2008)"},{"issue":"6","key":"942_CR14","doi-asserted-by":"publisher","first-page":"28:1","DOI":"10.1145\/2049697.2049702","volume":"58","author":"B Haeupler","year":"2011","unstructured":"Haeupler, B., Saha, B., Srinivasan, A.: New constructive aspects of the Lov\u00e1sz local lemma. J. ACM 58(6), 28:1-28:28 (2011)","journal-title":"J. ACM"},{"issue":"3","key":"942_CR15","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/BF01793010","volume":"11","author":"P Haxell","year":"1995","unstructured":"Haxell, P.: A condition for matchability in hypergraphs. Graphs Comb. 11(3), 245\u2013248 (1995)","journal-title":"Graphs Comb."},{"key":"942_CR16","unstructured":"Jansen, K., Rohwedder, L.: A note on the integrality gap of the configuration LP for restricted Santa Claus. CoRR arXiv:1807.03626 (2018)"},{"key":"942_CR17","volume-title":"Algorithm Design","author":"J Kleiberg","year":"2006","unstructured":"Kleiberg, J., Tardos, E.: Algorithm Design. Pearson\/Addison-Wesley, Reading (2006)"},{"key":"942_CR18","doi-asserted-by":"crossref","unstructured":"Lenstra, J., Shmoys, D., Tardos, \u00c9.: Approximation algorithms for scheduling unrelated parallel machines. In: Proceedings of the 28th IEEE Symposium on Foundations of Computer Science, pp. 217\u2013224 (1987)","DOI":"10.1109\/SFCS.1987.8"},{"key":"942_CR19","doi-asserted-by":"crossref","unstructured":"Polacek, L., Svensson, O.: Quasi-polynomial local search for restricted max-min fair allocation. In: 39th International Colloquium on Automata, Languages, and Programming, pp. 726\u2013737 (2012)","DOI":"10.1007\/978-3-642-31594-7_61"},{"key":"942_CR20","unstructured":"Saha, B., Srinivasan, A.: A new approximation technique for resource-allocation problems. In: Proceedings of the 1st Symposium on Innovations in Computer Science, pp. 342\u2013357 (2010)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00942-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-00942-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00942-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,23]],"date-time":"2022-06-23T11:04:31Z","timestamp":1655982271000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-00942-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,23]]},"references-count":20,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["942"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-00942-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,2,23]]},"assertion":[{"value":"8 September 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 January 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 February 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Code availability"}}]}}