{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T19:53:54Z","timestamp":1757620434894,"version":"3.44.0"},"publisher-location":"Singapore","reference-count":40,"publisher":"Springer Nature Singapore","isbn-type":[{"type":"print","value":"9789819502141"},{"type":"electronic","value":"9789819502158"}],"license":[{"start":{"date-parts":[[2025,8,1]],"date-time":"2025-08-01T00:00:00Z","timestamp":1754006400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,8,1]],"date-time":"2025-08-01T00:00:00Z","timestamp":1754006400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-981-95-0215-8_22","type":"book-chapter","created":{"date-parts":[[2025,7,31]],"date-time":"2025-07-31T16:25:18Z","timestamp":1753979118000},"page":"293-306","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Fair and\u00a0Efficient Graphical Resource Allocation with\u00a0Matching-Induced Utilities"],"prefix":"10.1007","author":[{"given":"Zheng","family":"Chen","sequence":"first","affiliation":[]},{"given":"Bin","family":"Deng","sequence":"additional","affiliation":[]},{"given":"Bo","family":"Li","sequence":"additional","affiliation":[]},{"given":"Minming","family":"Li","sequence":"additional","affiliation":[]},{"given":"Weidong","family":"Li","sequence":"additional","affiliation":[]},{"given":"Guochuan","family":"Zhang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,8,1]]},"reference":[{"key":"22_CR1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2023.103965","volume":"322","author":"G Amanatidis","year":"2023","unstructured":"Amanatidis, G., et al.: Fair division of indivisible goods: recent progress and open questions. Artif. Intell. 322, 103965 (2023)","journal-title":"Artif. Intell."},{"key":"22_CR2","doi-asserted-by":"crossref","unstructured":"Aziz, H., Bouveret, S., Caragiannis, I., Giagkousi, I., Lang, J.: Knowledge, fairness, and social constraints. In: Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, AAAI, pp. 4638\u20134645. AAAI Press (2018)","DOI":"10.1609\/aaai.v32i1.11590"},{"key":"22_CR3","doi-asserted-by":"crossref","unstructured":"Bansal, N., Sviridenko, M.: The Santa Claus problem. In: STOC, pp. 31\u201340 (2006)","DOI":"10.1145\/1132516.1132522"},{"key":"22_CR4","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1016\/j.dam.2015.01.008","volume":"196","author":"M Barketau","year":"2015","unstructured":"Barketau, M., Pesch, E., Shafransky, Y.M.: Minimizing maximum weight of subsets of a maximum matching in a bipartite graph. Discret. Appl. Math. 196, 4\u201319 (2015)","journal-title":"Discret. Appl. Math."},{"key":"22_CR5","doi-asserted-by":"crossref","unstructured":"Barman, S., Krishnamurthy, S.K.: Approximation algorithms for maximin fair division. ACM Trans. Economics Comput. 8(1), 5:1\u20135:28 (2020)","DOI":"10.1145\/3381525"},{"issue":"7","key":"22_CR6","doi-asserted-by":"publisher","first-page":"1069","DOI":"10.1007\/s00224-021-10039-8","volume":"65","author":"X Bei","year":"2021","unstructured":"Bei, X., Lu, X., Manurangsi, P., Suksompong, W.: The price of fairness for indivisible goods. Theory Comput. Syst. 65(7), 1069\u20131093 (2021)","journal-title":"Theory Comput. Syst."},{"key":"22_CR7","unstructured":"Bil\u00f2, V., et al.: Almost envy-free allocations with connected bundles. In: ITCS, vol.\u00a0124, pp. 14:1\u201314:21 (2019)"},{"key":"22_CR8","doi-asserted-by":"crossref","unstructured":"Blazej, V., Ganian, R., Knop, D., Pokorn\u00fd, J., Schierreich, S., Simonov, K.: The parameterized complexity of network microaggregation. In: Thirty-Seventh AAAI Conference on Artificial Intelligence, AAAI, pp. 6262\u20136270. AAAI Press (2023)","DOI":"10.1609\/aaai.v37i5.25771"},{"key":"22_CR9","unstructured":"Blazej, V., Knop, D., Pokorn\u00fd, J., Schierreich, S.: Equitable connected partition and structural parameters revisited: N-fold beats lenstra. In: 49th International Symposium on Mathematical Foundations of Computer Science, MFCS. LIPIcs, vol.\u00a0306, pp. 29:1\u201329:16. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2024)"},{"key":"22_CR10","doi-asserted-by":"crossref","unstructured":"Bouveret, S., Cechl\u00e1rov\u00e1, K., Elkind, E., Igarashi, A., Peters, D.: Fair division of a graph. In: IJCAI, pp. 135\u2013141. ijcai.org (2017)","DOI":"10.24963\/ijcai.2017\/20"},{"issue":"6","key":"22_CR11","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."},{"key":"22_CR12","doi-asserted-by":"crossref","unstructured":"Bulu\u00e7, A., Meyerhenke, H., Safro, I., Sanders, P., Schulz, C.: Recent advances in graph partitioning. In: Algorithm Engineering, Lecture Notes in Computer Science, vol.\u00a09220, pp. 117\u2013158 (2016)","DOI":"10.1007\/978-3-319-49487-6_4"},{"key":"22_CR13","doi-asserted-by":"crossref","unstructured":"Caragiannis, I., Micha, E., Shah, N.: A little charity guarantees fair connected graph partitioning. In: Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI, pp. 4908\u20134916. AAAI Press (2022)","DOI":"10.1609\/aaai.v36i5.20420"},{"key":"22_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.artint.2016.09.005","volume":"242","author":"Y Chevaleyre","year":"2017","unstructured":"Chevaleyre, Y., Endriss, U., Maudet, N.: Distributed fair allocation of indivisible goods. Artif. Intell. 242, 1\u201322 (2017)","journal-title":"Artif. Intell."},{"issue":"3","key":"22_CR15","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/s00446-022-00426-w","volume":"36","author":"V Dani","year":"2023","unstructured":"Dani, V., Gupta, A., Hayes, T.P., Pettie, S.: Wake up and join me! an energy-efficient algorithm for maximal matching in radio networks. Distributed Comput. 36(3), 373\u2013384 (2023)","journal-title":"Distributed Comput."},{"key":"22_CR16","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2022.103826","volume":"315","author":"E Eiben","year":"2023","unstructured":"Eiben, E., Ganian, R., Hamm, T., Ordyniak, S.: Parameterized complexity of envy-free resource allocation in social networks. Artif. Intell. 315, 103826 (2023)","journal-title":"Artif. Intell."},{"issue":"3","key":"22_CR17","doi-asserted-by":"publisher","first-page":"1148","DOI":"10.1007\/s00453-015-9992-y","volume":"74","author":"L Epstein","year":"2016","unstructured":"Epstein, L., Levin, A., Woeginger, G.J.: Vertex cover meets scheduling. Algorithmica 74(3), 1148\u20131173 (2016)","journal-title":"Algorithmica"},{"key":"22_CR18","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/j.disopt.2015.01.001","volume":"16","author":"B Farbstein","year":"2015","unstructured":"Farbstein, B., Levin, A.: Min-max cover of a graph with a small number of parts. Discret. Optim. 16, 51\u201361 (2015)","journal-title":"Discret. Optim."},{"key":"22_CR19","doi-asserted-by":"crossref","unstructured":"Flanigan, B., G\u00f6lz, P., Gupta, A., Hennig, B., Procaccia, A.D.: Fair algorithms for selecting citizens\u2019 assemblies. Nature 1\u20135 (2021)","DOI":"10.1038\/s41586-021-03788-6"},{"key":"22_CR20","unstructured":"Foley, D.K.: Resource allocation and the public sector. Yale Econ. Essays 7 (1967)"},{"key":"22_CR21","doi-asserted-by":"crossref","unstructured":"Garg, J., Taki, S.: An improved approximation algorithm for maximin shares. Artif. Intell. 300 (2021)","DOI":"10.1016\/j.artint.2021.103547"},{"key":"22_CR22","doi-asserted-by":"crossref","unstructured":"Ghodsi, M., Hajiaghayi, M.T., 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, EC, pp. 539\u2013556. ACM (2018)","DOI":"10.1145\/3219166.3219238"},{"issue":"2","key":"22_CR23","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1145\/2728732.2728738","volume":"13","author":"JR Goldman","year":"2014","unstructured":"Goldman, J.R., Procaccia, A.D.: Spliddit: unleashing fair division algorithms. SIGecom Exch. 13(2), 41\u201346 (2014)","journal-title":"SIGecom Exch."},{"key":"22_CR24","doi-asserted-by":"crossref","unstructured":"Igarashi, A.: How to cut a discrete cake fairly. In: Thirty-Seventh AAAI Conference on Artificial Intelligence, AAAI. pp. 5681\u20135688. AAAI Press (2023)","DOI":"10.1609\/aaai.v37i5.25705"},{"key":"22_CR25","doi-asserted-by":"crossref","unstructured":"Igarashi, A., Peters, D.: Pareto-optimal allocation of indivisible goods with connectivity constraints. In: Thirty-Third AAAI Conference on Artificial Intelligence, AAAI, pp. 2045\u20132052. AAAI Press (2019)","DOI":"10.1609\/aaai.v33i01.33012045"},{"issue":"2","key":"22_CR26","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1007\/s00453-012-9740-5","volume":"69","author":"MR Khani","year":"2014","unstructured":"Khani, M.R., Salavatipour, M.R.: Improved approximation algorithms for the min-max tree cover and bounded tree cover problems. Algorithmica 69(2), 443\u2013460 (2014)","journal-title":"Algorithmica"},{"issue":"1","key":"22_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ejor.2015.07.020","volume":"249","author":"\u00c7 Ko\u00e7","year":"2016","unstructured":"Ko\u00e7, \u00c7., Bektas, T., Jabali, O., Laporte, G.: Thirty years of heterogeneous vehicle routing. Eur. J. Oper. Res. 249(1), 1\u201321 (2016)","journal-title":"Eur. J. Oper. Res."},{"issue":"3","key":"22_CR28","doi-asserted-by":"publisher","first-page":"745","DOI":"10.1016\/j.ejor.2015.06.041","volume":"247","author":"D Kress","year":"2015","unstructured":"Kress, D., Meiswinkel, S., Pesch, E.: The partitioning min-max weighted matching problem. Eur. J. Oper. Res. 247(3), 745\u2013754 (2015)","journal-title":"Eur. J. Oper. Res."},{"issue":"2","key":"22_CR29","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1145\/3140756","volume":"65","author":"D Kurokawa","year":"2018","unstructured":"Kurokawa, D., Procaccia, A., Wang, J.: Fair enough: guaranteeing approximate maximin shares. J. ACM 65(2), 8 (2018)","journal-title":"J. ACM"},{"key":"22_CR30","doi-asserted-by":"crossref","unstructured":"Li, L., Micha, E., Nikolov, A., Shah, N.: Partitioning friends fairly. In: Thirty-Seventh AAAI Conference on Artificial Intelligence, AAAI, pp. 5747\u20135754. AAAI Press (2023)","DOI":"10.1609\/aaai.v37i5.25713"},{"key":"22_CR31","doi-asserted-by":"crossref","unstructured":"Lipton, R.J., Markakis, E., Mossel, E., Saberi, A.: On approximately fair allocations of indivisible goods. In: EC, pp. 125\u2013131. ACM (2004)","DOI":"10.1145\/988772.988792"},{"key":"22_CR32","doi-asserted-by":"crossref","unstructured":"Lov\u00e1sz, L., Plummer, M.D.: Matching theory, vol.\u00a0367. American Mathematical Soc. (2009)","DOI":"10.1090\/chel\/367"},{"issue":"3","key":"22_CR33","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1016\/j.ejor.2020.12.059","volume":"293","author":"FK Miyazawa","year":"2021","unstructured":"Miyazawa, F.K., Moura, P., Ota, M.J., Wakabayashi, Y.: Partitioning a graph into balanced connected classes: formulations, separation and experiments. Eur. J. Oper. Res. 293(3), 826\u2013836 (2021)","journal-title":"Eur. J. Oper. Res."},{"key":"22_CR34","doi-asserted-by":"crossref","unstructured":"Moulin, H.: Fair Division and Collective Welfare. MIT Press (2003)","DOI":"10.7551\/mitpress\/2954.001.0001"},{"key":"22_CR35","unstructured":"Rathinam, S., Ravi, R., Bae, J., Sundar, K.: Primal-dual 2-approximation algorithm for the monotonic multiple depot heterogeneous traveling salesman problem. In: SWAT. LIPIcs, vol.\u00a0162, pp. 33:1\u201333:13 (2020)"},{"key":"22_CR36","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/j.dam.2019.01.036","volume":"260","author":"W Suksompong","year":"2019","unstructured":"Suksompong, W.: Fairly allocating contiguous blocks of indivisible items. Discret. Appl. Math. 260, 227\u2013236 (2019)","journal-title":"Discret. Appl. Math."},{"issue":"2","key":"22_CR37","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. SIGecom Exch. 19(2), 46\u201361 (2021)","journal-title":"SIGecom Exch."},{"key":"22_CR38","doi-asserted-by":"crossref","unstructured":"Traub, V., Tr\u00f6bst, T.: A fast (2 + 2\/7)-approximation algorithm for capacitated cycle covering. In: IPCO, pp. 391\u2013404. Springer (2020)","DOI":"10.1007\/978-3-030-45771-6_30"},{"key":"22_CR39","doi-asserted-by":"crossref","unstructured":"Wang, F., Li, B.: Fair surveillance assignment problem. In: WWW, pp. 178\u2013186. ACM (2024)","DOI":"10.1145\/3589334.3645613"},{"issue":"2","key":"22_CR40","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/s10107-005-0611-6","volume":"106","author":"H Yaman","year":"2006","unstructured":"Yaman, H.: Formulations and valid inequalities for the heterogeneous vehicle routing problem. Math. Program. 106(2), 365\u2013390 (2006)","journal-title":"Math. Program."}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-95-0215-8_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T09:33:17Z","timestamp":1757323997000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-95-0215-8_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,1]]},"ISBN":["9789819502141","9789819502158"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/978-981-95-0215-8_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025,8,1]]},"assertion":[{"value":"1 August 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOON","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computing and Combinatorics Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Chengdu","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 August 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 August 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"31","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoon0","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/tcsuestc.com\/cocoon2025\/index.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}