{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,9]],"date-time":"2025-05-09T07:51:49Z","timestamp":1746777109381,"version":"3.37.3"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,2,27]],"date-time":"2023-02-27T00:00:00Z","timestamp":1677456000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,2,27]],"date-time":"2023-02-27T00:00:00Z","timestamp":1677456000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100004663","name":"Ministry of Science and Technology, Taiwan","doi-asserted-by":"publisher","award":["105-2628-E-007-010-MY3, 109-2634-F-007-018"],"award-info":[{"award-number":["105-2628-E-007-010-MY3, 109-2634-F-007-018"]}],"id":[{"id":"10.13039\/501100004663","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Research Grants Council, Hong Kong, China","award":["16207419"],"award-info":[{"award-number":["16207419"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2024,2]]},"DOI":"10.1007\/s00453-023-01105-3","type":"journal-article","created":{"date-parts":[[2023,2,27]],"date-time":"2023-02-27T13:03:03Z","timestamp":1677502983000},"page":"485-504","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Polynomial-time Combinatorial Algorithm for General Max\u2013Min Fair Allocation"],"prefix":"10.1007","volume":"86","author":[{"given":"Sheng-Yen","family":"Ko","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ho-Lin","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3557-9935","authenticated-orcid":false,"given":"Siu-Wing","family":"Cheng","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wing-Kai","family":"Hon","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chung-Shou","family":"Liao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,2,27]]},"reference":[{"issue":"3","key":"1105_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3070694","volume":"13","author":"C Annamalai","year":"2017","unstructured":"Annamalai, C., Kalaitzis, C., Svensson, O.: Combinatorial algorithm for restricted max\u2013min fair allocation. ACM Trans. Algorithms 13(3), 1\u201328 (2017)","journal-title":"ACM Trans. Algorithms"},{"key":"1105_CR2","doi-asserted-by":"crossref","unstructured":"Argyris, N., Karsu, $$\\ddot{O}$$., Yavuz, M.: Fair resource allocation: using welfare-based dominance constraints. Eur. J. Oper. Res., 297(2), 560\u2013578 (2022)","DOI":"10.1016\/j.ejor.2021.05.003"},{"issue":"3","key":"1105_CR3","doi-asserted-by":"publisher","first-page":"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), 1\u20139 (2012)","journal-title":"ACM Trans. Algorithms"},{"key":"1105_CR4","doi-asserted-by":"crossref","unstructured":"Asadpour, A., Saberi, A.: An approximation algorithm for max\u2013min fair allocation of indivisible goods. In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pp. 114\u2013121 (2007)","DOI":"10.1145\/1250790.1250808"},{"key":"1105_CR5","doi-asserted-by":"crossref","unstructured":"Azar, Y., Epstein, L.: Approximation schemes for covering and scheduling on related machines. In: Proceedings of the International Workshop on Approximation Algorithms for Combinatorial Optimization, pp. 39\u201347 (1998)","DOI":"10.1007\/BFb0053962"},{"key":"1105_CR6","doi-asserted-by":"crossref","unstructured":"Bansal, N., Sviridenko, M.: The Santa Claus problem. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pp. 31\u201340 (2006)","DOI":"10.1145\/1132516.1132522"},{"issue":"3","key":"1105_CR7","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. ACM SIGecom Exchanges 5(3), 11\u201318 (2005)","journal-title":"ACM SIGecom Exchanges"},{"key":"1105_CR8","doi-asserted-by":"crossref","unstructured":"Chakrabarty, D., Chuzhoy, J., Khanna, S.: On allocating goods to maximize fairness. In: Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, pp. 107\u2013116 (2009)","DOI":"10.1109\/FOCS.2009.51"},{"key":"1105_CR9","unstructured":"Cheng, S.-Wi., Mao, Y.: Restricted max\u2013min fair allocation. In: Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, pp. 37:1\u201337:13 (2018)"},{"key":"1105_CR10","unstructured":"Cheng, S.-W., Mao, Y.: Restricted max\u2013min allocation: approximation and integrality gap. In: Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, pp. 38:1\u201338:13 (2019)"},{"key":"1105_CR11","doi-asserted-by":"publisher","first-page":"1835","DOI":"10.1007\/s00453-022-00942-y","volume":"84","author":"S-W Cheng","year":"2022","unstructured":"Cheng, S.-W., Mao, Y.: Restricted max\u2013min allocation: approximation and integrality gap. Algorithmica 84, 1835\u20131874 (2022)","journal-title":"Algorithmica"},{"issue":"5","key":"1105_CR12","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/0167-6377(92)90004-M","volume":"11","author":"J Csirik","year":"1992","unstructured":"Csirik, J., Kellerer, H., Woeginger, G.: The exact LPT-bound for maximizing the minimum completion time. Oper. Res. Lett. 11(5), 281\u2013287 (1992)","journal-title":"Oper. Res. Lett."},{"key":"1105_CR13","doi-asserted-by":"crossref","unstructured":"Davies, S., Tothvoss, 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":"1105_CR14","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1137\/0603019","volume":"3","author":"B Deuermeyer","year":"1982","unstructured":"Deuermeyer, B., Friesen, D., Langston, M.: Scheduling to maximize the minimum processor finish time in a multiprocessor system. SIAM J. Algebraic Discrete Methods 3, 190\u2013196 (1982)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"issue":"2","key":"1105_CR15","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/j.tcs.2005.02.008","volume":"339","author":"Y He","year":"2005","unstructured":"He, Y., Jiang, Y.: Optimal semi-online preemptive algorithms for machine covering on two uniform machines. Theoret. Comput. Sci. 339(2), 293\u2013314 (2005)","journal-title":"Theoret. Comput. Sci."},{"key":"1105_CR16","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1023\/A:1013855712183","volume":"6","author":"Y He","year":"2002","unstructured":"He, Y., Tan, Z.: Ordinal on-line scheduling for maximizing the minimum machine completion time. J. Comb. Optim. 6, 199\u2013206 (2002)","journal-title":"J. Comb. Optim."},{"key":"1105_CR17","doi-asserted-by":"crossref","unstructured":"Lenstra, J.K., Shmoys, D.B, Tardos, E.: Approximation algorithms for scheduling unrelated parallel machines. In: Proceedings of the 28th Annual Symposium on Foundations of Computer Science, pp. 217\u2013224 (1987)","DOI":"10.1109\/SFCS.1987.8"},{"issue":"2","key":"1105_CR18","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1016\/j.ejor.2011.10.029","volume":"218","author":"E Medernach","year":"2012","unstructured":"Medernach, E., Sanlaville, E.: Fair resource allocation for different scenarios of demands. Eur. J. Oper. Res. 218(2), 339\u2013350 (2012)","journal-title":"Eur. J. Oper. Res."},{"issue":"4","key":"1105_CR19","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1109\/SURV.2008.080403","volume":"10","author":"D Nace","year":"2008","unstructured":"Nace, D., Pioro, M.: Max\u2013min fairness and its applications to routing and load-balancing in communication networks: a tutorial. IEEE Commun. Surveys Tutorials 10(4), 5\u201317 (2008)","journal-title":"IEEE Commun. Surveys Tutorials"},{"key":"1105_CR20","doi-asserted-by":"publisher","first-page":"680","DOI":"10.1002\/rsa.20756","volume":"52","author":"B Saha","year":"2018","unstructured":"Saha, B., Srinivasan, A.: A new approximation technique for resource-allocation problems. Random Struct. Algorithms 52, 680\u2013715 (2018)","journal-title":"Random Struct. Algorithms"},{"issue":"2","key":"1105_CR21","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1016\/j.ejor.2009.05.033","volume":"202","author":"A Sbihi","year":"2010","unstructured":"Sbihi, A.: A cooperative local search-based algorithm for the multiple-scenario max\u2013min knapsack problem. Eur. J. Oper. Res. 202(2), 339\u2013346 (2010)","journal-title":"Eur. J. Oper. Res."},{"issue":"4","key":"1105_CR22","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0167-6377(96)00055-7","volume":"20","author":"GJ Woeginger","year":"1997","unstructured":"Woeginger, G.J.: A polynomial-time approximation scheme for maximizing the minimum machine completion time. Oper. Res. Lett. 20(4), 149\u2013154 (1997)","journal-title":"Oper. Res. Lett."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01105-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-023-01105-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01105-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,24]],"date-time":"2024-01-24T09:10:37Z","timestamp":1706087437000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-023-01105-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,2,27]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,2]]}},"alternative-id":["1105"],"URL":"https:\/\/doi.org\/10.1007\/s00453-023-01105-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2023,2,27]]},"assertion":[{"value":"28 January 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 February 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 February 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"none declared.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}