{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,19]],"date-time":"2026-07-19T10:02:50Z","timestamp":1784455370414,"version":"3.55.0"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2024,8,22]],"date-time":"2024-08-22T00:00:00Z","timestamp":1724284800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,8,22]],"date-time":"2024-08-22T00:00:00Z","timestamp":1724284800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"name":"Scientific Research and Innovation Project of Postgraduate Students in the Academic Degree of Yunnan University","award":["KC-23236212"],"award-info":[{"award-number":["KC-23236212"]}]},{"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":["Optim Lett"],"published-print":{"date-parts":[[2025,6]]},"DOI":"10.1007\/s11590-024-02145-6","type":"journal-article","created":{"date-parts":[[2024,8,23]],"date-time":"2024-08-23T13:33:59Z","timestamp":1724420039000},"page":"955-968","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["The budgeted maximin share allocation problem"],"prefix":"10.1007","volume":"19","author":[{"given":"Bin","family":"Deng","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3094-4347","authenticated-orcid":false,"given":"Weidong","family":"Li","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2024,8,22]]},"reference":[{"key":"2145_CR1","doi-asserted-by":"publisher","unstructured":"Akrami, H., Sharma, E., Taki, S.: Simplification and improvement of MMS approximation. In: Proceedings of the 32th International Joint Conference on Artificial Intelligence, pp. 2485\u20132493 (2023). https:\/\/doi.org\/10.24963\/ijcai.2023\/276","DOI":"10.24963\/ijcai.2023\/276"},{"key":"2145_CR2","doi-asserted-by":"crossref","unstructured":"Akrami, H., Garg, J., Taki, S.: Improving approximation guarantees for maximin share. Preprint at arXiv:2307.12916 (2023)","DOI":"10.1145\/3670865.3673544"},{"key":"2145_CR3","doi-asserted-by":"publisher","unstructured":"Akrami, H., Garg, J.: Breaking the $$3\/4$$ barrier for approximate maximin share. In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 74\u201391 (2024). https:\/\/doi.org\/10.1137\/1.9781611977912.4","DOI":"10.1137\/1.9781611977912.4"},{"key":"2145_CR4","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2023.103965","author":"G Amanatidis","year":"2023","unstructured":"Amanatidis, G., Aziz, H., Birmpas, G., Filos-Ratsikas, A., Li, B., Moulin, H., Voudouris, A.A., Wu, X.: Fair division of indivisible goods: recent progress and open questions. Artif. Intell. (2023). https:\/\/doi.org\/10.1016\/j.artint.2023.103965","journal-title":"Artif. Intell."},{"issue":"4","key":"2145_CR5","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.: Approximation algorithms for computing maximin share allocations. ACM Trans. Algorithms 13(4), 1\u201328 (2017). https:\/\/doi.org\/10.1145\/3147173","journal-title":"ACM Trans. Algorithms"},{"issue":"7","key":"2145_CR6","doi-asserted-by":"publisher","first-page":"2970","DOI":"10.1145\/1250790.1250808","volume":"39","author":"A Asadpour","year":"2010","unstructured":"Asadpour, A., Saberi, A.: An approximation algorithm for max-min fair allocation of indivisible goods. SIAM J. Comput. 39(7), 2970\u20132989 (2010). https:\/\/doi.org\/10.1145\/1250790.1250808","journal-title":"SIAM J. Comput."},{"issue":"1","key":"2145_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3381525","volume":"8","author":"S Barman","year":"2020","unstructured":"Barman, S., Krishnamurthy, S.: Approximation algorithms for maximin fair division. ACM Trans. Econ. Comput. 8(1), 1\u201328 (2020). https:\/\/doi.org\/10.1145\/3381525","journal-title":"ACM Trans. Econ. Comput."},{"key":"2145_CR8","doi-asserted-by":"publisher","unstructured":"Barman, S., Khan, A., Shyam, S., Sreenivas, K.: Finding fair allocations under budget constraints. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 37, no. 5, pp. 5481\u20135489 (2023). https:\/\/doi.org\/10.1609\/aaai.v37i5.25681","DOI":"10.1609\/aaai.v37i5.25681"},{"key":"2145_CR9","doi-asserted-by":"publisher","unstructured":"Barman, S., Khan, A., Shyam, S., Sreenivas, K.: Guaranteeing envy-freeness under generalized assignment constraints. In: Proceedings of the 24th ACM Conference on Economics and Computation, pp. 242\u2013269 (2023). https:\/\/doi.org\/10.1145\/3580507.3597698","DOI":"10.1145\/3580507.3597698"},{"issue":"3","key":"2145_CR10","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1145\/1120680.1120683","volume":"5","author":"I Bezakova","year":"2005","unstructured":"Bezakova, I., Dani, V.: Allocating indivisible goods. ACM SIGecom Exch. 5(3), 11\u201318 (2005). https:\/\/doi.org\/10.1145\/1120680.1120683","journal-title":"ACM SIGecom Exch."},{"key":"2145_CR11","doi-asserted-by":"crossref","unstructured":"Biswas, A., Barman, A.: Fair division under cardinality constraints. In: Proceedings of the 27th International Joint Conference on Artificial Intelligence, pp. 91\u201397 (2018)","DOI":"10.24963\/ijcai.2018\/13"},{"issue":"6","key":"2145_CR12","doi-asserted-by":"publisher","first-page":"1061","DOI":"10.1086\/664613","volume":"119","author":"E Budish","year":"2011","unstructured":"Budish, E.: The combinatorial assignment problem: approximate competitive equilibrium from equal incomes. J. Polit. Econ. 119(6), 1061\u20131103 (2011)","journal-title":"J. Polit. Econ."},{"issue":"2","key":"2145_CR13","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1137\/S1052623498348481","volume":"11","author":"A Caprara","year":"2000","unstructured":"Caprara, A., Kellerer, H., Pferschy, U.: The multiple subset sum problem. SIAM J. Optim. 11(2), 308\u2013319 (2000). https:\/\/doi.org\/10.1137\/S1052623498348481","journal-title":"SIAM J. Optim."},{"key":"2145_CR14","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1109\/FOCS.2009.51","DOI":"10.1109\/FOCS.2009.51"},{"key":"2145_CR15","doi-asserted-by":"publisher","unstructured":"Chen, L., Lian, J., Mao, Y., Zhang, G.: A nearly quadratic-time FPTAS for knapsack. In: Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pp. 283\u2013294 (2024). https:\/\/doi.org\/10.1145\/3618260.3649730","DOI":"10.1145\/3618260.3649730"},{"key":"2145_CR16","doi-asserted-by":"publisher","unstructured":"Feige, U., Sapir, A., Tauber, L.: A tight negative example for MMS fair allocations, In: Proceedings of the International Conference on Web and Internet Economics, pp. 355-372 (2021). https:\/\/doi.org\/10.1007\/978-3-030-94676-0_20","DOI":"10.1007\/978-3-030-94676-0_20"},{"key":"2145_CR17","doi-asserted-by":"publisher","unstructured":"Garg, J., McGlaughlin, P., Taki, S.: Approximating maximin share allocations. In: 2nd Symposium on Simplicity in Algorithms, vol. 69, pp. 20:1\u201320:11 (2019). https:\/\/doi.org\/10.4230\/OASIcs.SOSA.2019.20","DOI":"10.4230\/OASIcs.SOSA.2019.20"},{"key":"2145_CR18","doi-asserted-by":"publisher","DOI":"10.1145\/3391403.3399526","author":"J Garg","year":"2021","unstructured":"Garg, J., Taki, S.: An improved approximation algorithm for maximin shares. Artif. Intell. (2021). https:\/\/doi.org\/10.1145\/3391403.3399526","journal-title":"Artif. Intell."},{"key":"2145_CR19","doi-asserted-by":"publisher","unstructured":"Garbea, M., Gkatzelis, V., Tan, X.: EFx budget-feasible allocations with high Nash welfare. In: 26th European Conference on Artificial Intelligence, pp. 795\u2013802 (2023). https:\/\/doi.org\/10.3233\/FAIA230346","DOI":"10.3233\/FAIA230346"},{"key":"2145_CR20","volume-title":"Computers and intractability: A guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability: A guide to the theory of NP-completeness. W.H. Freeman, San Francisco (1979)"},{"key":"2145_CR21","unstructured":"Gan, J., Li, B., Wu, X.: Approximation algorithm for computing budget-feasible EF1 allocations. In: Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, pp. 170\u2013178 (2023)"},{"key":"2145_CR22","doi-asserted-by":"publisher","unstructured":"Ghodsi, M., HajiAghayi, M., Seddighin, M., Seddighin, S., Yami, H.: Fair allocation of indivisible goods: improvements and generalizations. In: Proceedings of the 2018 ACM Conference on Economics and Computation, pp. 539\u2013556 (2018). https:\/\/doi.org\/10.1145\/3219166.3219238","DOI":"10.1145\/3219166.3219238"},{"key":"2145_CR23","doi-asserted-by":"publisher","DOI":"10.3390\/math11163616","author":"H Guo","year":"2023","unstructured":"Guo, H., Li, W., Deng, B.: A survey on fair allocation of chores. Mathematics (2023). https:\/\/doi.org\/10.3390\/math11163616","journal-title":"Mathematics"},{"key":"2145_CR24","doi-asserted-by":"publisher","unstructured":"Hummel, H., Hetland, M.L.: Maximin shares under cardinality constraints. In: Proceedings of the European Conference on Multi-Agent Systems, pp. 188\u2013206 (2022). https:\/\/doi.org\/10.1007\/978-3-031-20614-6_11","DOI":"10.1007\/978-3-031-20614-6_11"},{"key":"2145_CR25","doi-asserted-by":"crossref","unstructured":"Hummel, H.: Maximin shares in hereditary set systems. Preprint at arXiv: 2404.11582 (2024)","DOI":"10.1145\/3727149"},{"issue":"2","key":"2145_CR26","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1007\/s00453-023-01105-3","volume":"86","author":"SY Ko","year":"2024","unstructured":"Ko, S.Y., Chen, H.L., Cheng, S.W., Hon, W.K., Liao, C.S.: Polynomial-time combinatorial algorithm for general max-min fair allocation. Algorithmica 86(2), 485\u2013504 (2024). https:\/\/doi.org\/10.1007\/s00453-023-01105-3","journal-title":"Algorithmica"},{"issue":"2","key":"2145_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-023-01105-3","volume":"65","author":"D Kurokawa","year":"2018","unstructured":"Kurokawa, D., Procaccia, A., Wang, J.: Fair enough: guaranteeing approximate maximin shares. J. ACM 65(2), 1\u201327 (2018). https:\/\/doi.org\/10.1007\/s00453-023-01105-3","journal-title":"J. ACM"},{"issue":"4","key":"2145_CR28","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(4), 680\u2013715 (2018). https:\/\/doi.org\/10.1002\/rsa.20756","journal-title":"Random Struct. Algorithms"},{"issue":"2","key":"2145_CR29","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1145\/3505156.3505162","volume":"19","author":"W Suksompong","year":"2021","unstructured":"Suksompong, W.: Constraints in fair division. ACM SIGecom Exch. 19(2), 46\u201361 (2021). https:\/\/doi.org\/10.1145\/3505156.3505162","journal-title":"ACM SIGecom Exch."},{"key":"2145_CR30","unstructured":"Wang, S., Zhou, T., Lavania, C., Bilmes, J.: Constrained robust submodular partitioning. In: Advances in Neural Information Processing Systems, vol. 34, pp. 2721\u20132732 (2021)"},{"key":"2145_CR31","doi-asserted-by":"crossref","unstructured":"Wu, X., Li, B., Gan, J.: Budget-feasible maximum Nash social welfare is almost envy-free. In: International Joint Conferences on Artificial Intelligence, pp. 465\u2013471 (2021)","DOI":"10.24963\/ijcai.2021\/65"}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-024-02145-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11590-024-02145-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-024-02145-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,9]],"date-time":"2025-05-09T07:36:53Z","timestamp":1746776213000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11590-024-02145-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,22]]},"references-count":31,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["2145"],"URL":"https:\/\/doi.org\/10.1007\/s11590-024-02145-6","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"value":"1862-4472","type":"print"},{"value":"1862-4480","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,8,22]]},"assertion":[{"value":"7 September 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 August 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 August 2024","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 known competing financial interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}