{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T19:21:43Z","timestamp":1757618503185,"version":"3.44.0"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,7,3]],"date-time":"2025-07-03T00:00:00Z","timestamp":1751500800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,7,3]],"date-time":"2025-07-03T00:00:00Z","timestamp":1751500800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["12071417"],"award-info":[{"award-number":["12071417"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2025,8]]},"DOI":"10.1007\/s10878-025-01331-1","type":"journal-article","created":{"date-parts":[[2025,7,3]],"date-time":"2025-07-03T04:36:35Z","timestamp":1751517395000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Approximate maximin share allocation for indivisible goods under a knapsack constraint"],"prefix":"10.1007","volume":"50","author":[{"given":"Bin","family":"Deng","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3094-4347","authenticated-orcid":false,"given":"Weidong","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,7,3]]},"reference":[{"key":"1331_CR1","doi-asserted-by":"crossref","unstructured":"Akrami H, Garg J (2024) Breaking the $$3\/4$$ barrier for approximate maximin share. In: Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms, pp 74\u201391. SIAM","DOI":"10.1137\/1.9781611977912.4"},{"key":"1331_CR2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2023.103965","volume":"322","author":"G Amanatidis","year":"2023","unstructured":"Amanatidis G, Aziz H, Birmpas G et al (2023) Fair division of indivisible goods: Recent progress and open questions. Artif Intell 322:103965","journal-title":"Artif Intell"},{"issue":"4","key":"1331_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3147173","volume":"13","author":"G Amanatidis","year":"2017","unstructured":"Amanatidis G, Markakis E, Nikzad A, Saberi A (2017) Approximation algorithms for computing maximin share allocations. ACM Trans Algorithms 13(4):1\u201328","journal-title":"ACM Trans Algorithms"},{"issue":"7","key":"1331_CR4","doi-asserted-by":"publisher","first-page":"2970","DOI":"10.1137\/080723491","volume":"39","author":"A Asadpour","year":"2010","unstructured":"Asadpour A, Saberi A (2010) An approximation algorithm for max-min fair allocation of indivisible goods. SIAM J Comput 39(7):2970\u20132989","journal-title":"SIAM J Comput"},{"key":"1331_CR5","doi-asserted-by":"crossref","unstructured":"Bansal N, Sviridenko M (2006) The Santa Claus problem. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pp 31\u201340. ACM","DOI":"10.1145\/1132516.1132522"},{"issue":"3","key":"1331_CR6","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1145\/1120680.1120683","volume":"5","author":"I Bezakova","year":"2005","unstructured":"Bezakova I, Dani V (2005) Allocating indivisible goods. ACM SIGecom Exch 5(3):11\u201318","journal-title":"ACM SIGecom Exch"},{"issue":"2","key":"1331_CR7","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/s10458-015-9287-3","volume":"30","author":"S Bouveret","year":"2016","unstructured":"Bouveret S, Lema\u00eetre M (2016) Characterizing conflicts in fair division of indivisible goods using a scale of criteria. Auton Agent Multi-Agent Syst 30(2):259\u2013290","journal-title":"Auton Agent Multi-Agent Syst"},{"issue":"6","key":"1331_CR8","doi-asserted-by":"publisher","first-page":"1061","DOI":"10.1086\/664613","volume":"119","author":"E Budish","year":"2011","unstructured":"Budish E (2011) The combinatorial assignment problem: approximate competitive equilibrium from equal incomes. J Polit Econ 119(6):1061\u20131103","journal-title":"J Polit Econ"},{"key":"1331_CR9","doi-asserted-by":"crossref","unstructured":"Chakrabarty D, Chuzhoy J, Khanna S (2009) On allocating goods to maximize fairness. In: 50th Annual IEEE Symposium on Foundations of Computer Science, 107\u2013116. IEEE","DOI":"10.1109\/FOCS.2009.51"},{"key":"1331_CR10","doi-asserted-by":"crossref","unstructured":"Deng B, Li W (2025) The budgeted maximin share allocation problem. Optim Lett 19:955\u2013968","DOI":"10.1007\/s11590-024-02145-6"},{"issue":"1","key":"1331_CR11","first-page":"147","volume":"16","author":"Y Ding","year":"2021","unstructured":"Ding Y, Li K, Liu C, Tang Z, Li K (2021) Budget-constrained service allocation optimization for mobile edge computing. IEEE Trans Serv Comput 16(1):147\u201361","journal-title":"IEEE Trans Serv Comput"},{"key":"1331_CR12","doi-asserted-by":"crossref","unstructured":"Feige U, Sapir A, Tauber L (2021) A tight negative example for MMS fair allocations. In: International Conference on Web and Internet Economics, pp 355\u2013372. Springer","DOI":"10.1007\/978-3-030-94676-0_20"},{"key":"1331_CR13","unstructured":"Feige U, Norkin A (2022) Improved maximin fair allocation of indivisible items to three agents. arXiv preprint arXiv:2205.05363"},{"key":"1331_CR14","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2021.103547","volume":"300","author":"J Garg","year":"2021","unstructured":"Garg J, Taki S (2021) An improved approximation algorithm for maximin shares. Artif Intell 300:103547","journal-title":"Artif Intell"},{"issue":"3","key":"1331_CR15","doi-asserted-by":"publisher","first-page":"1038","DOI":"10.1287\/moor.2020.1096","volume":"46","author":"M Ghodsi","year":"2021","unstructured":"Ghodsi M, HajiAghayi M, Seddighin M, Seddighin S, Yami H (2021) Fair allocation of indivisible goods: Improvement. Math Oper Res 46(3):1038\u20131053","journal-title":"Math Oper Res"},{"key":"1331_CR16","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2021.103633","volume":"303","author":"M Ghodsi","year":"2022","unstructured":"Ghodsi M, HajiAghayi M, Seddighin M, Seddighin S, Yami H (2022) Fair allocation of indivisible goods: Beyond additive valuations. Artif Intell 303:103633","journal-title":"Artif Intell"},{"issue":"16","key":"1331_CR17","doi-asserted-by":"publisher","first-page":"3616","DOI":"10.3390\/math11163616","volume":"11","author":"H Guo","year":"2023","unstructured":"Guo H, Li W, Deng B (2023) A survey on fair allocation of chores. Mathematics 11(16):3616","journal-title":"Mathematics"},{"key":"1331_CR18","doi-asserted-by":"crossref","unstructured":"Hummel H (2025) Maximin shares in hereditary set systems. ACM Trans Econ Comput 13(3):12:1\u201312:33","DOI":"10.1145\/3727149"},{"issue":"3","key":"1331_CR19","doi-asserted-by":"publisher","first-page":"948","DOI":"10.1016\/j.ejor.2016.09.013","volume":"264","author":"A Holzapfel","year":"2018","unstructured":"Holzapfel A, Kuhn H, Sternbeck MG (2018) Product allocation to different types of distribution center in retail logistics networks. Eur J Oper Res 264(3):948\u201366","journal-title":"Eur J Oper Res"},{"issue":"2","key":"1331_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3140756","volume":"65","author":"D Kurokawa","year":"2018","unstructured":"Kurokawa D, Procaccia A, Wang J (2018) Fair enough: Guaranteeing approximate maximin shares. J ACM 65(2):1\u201327","journal-title":"J ACM"},{"issue":"2","key":"1331_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3434410","volume":"9","author":"Z Li","year":"2021","unstructured":"Li Z, Vetta A (2021) The fair division of hereditary set systems. ACM Trans Econ Comput 9(2):1\u201319","journal-title":"ACM Trans Econ Comput"},{"key":"1331_CR22","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2023.104049","volume":"327","author":"M Seddighin","year":"2024","unstructured":"Seddighin M, Seddighin S (2024) Improved maximin guarantees for subadditive and fractionally subadditive fair allocation problem. Artif Intell 327:104049","journal-title":"Artif Intell"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-025-01331-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-025-01331-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-025-01331-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,7]],"date-time":"2025-09-07T00:38:06Z","timestamp":1757205486000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-025-01331-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,3]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,8]]}},"alternative-id":["1331"],"URL":"https:\/\/doi.org\/10.1007\/s10878-025-01331-1","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2025,7,3]]},"assertion":[{"value":"14 June 2025","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 July 2025","order":2,"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"}}],"article-number":"5"}}