{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:38:09Z","timestamp":1759639089464,"version":"3.41.2"},"reference-count":25,"publisher":"World Scientific Pub Co Pte Ltd","issue":"05","funder":[{"DOI":"10.13039\/501100001809","name":"National Nature Science Foundation of China","doi-asserted-by":"crossref","award":["12071460"],"award-info":[{"award-number":["12071460"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Guangxi Key Laboratory of Cryptography and Information Security","award":["GCIS202116"],"award-info":[{"award-number":["GCIS202116"]}]},{"name":"National Key Research and Development Project of China","award":["2021YFF0901100"],"award-info":[{"award-number":["2021YFF0901100"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2025,8]]},"abstract":"<jats:p> This paper studies the problem of dividing [Formula: see text] indivisible items among [Formula: see text] agents fairly and efficiently. Specifically, this research concentrates on pairwise maximin share (PMMS), which is defined to be the maximum value that an agent can guarantee for herself if she were to repartition the items with another agent and receive the bundle with the minimum value. PMMS is an important concept in the fair division. However, whether PMMS for indivisible items exists is still open. This work concentrates on PMMS by proving the existence of PMMS on linear graphs with binary valuation functions. Besides, this paper designs an algorithm to approximate PMMS in the case where different agents have identical valuations among the same items, achieving a ratio strictly greater than 0.8, which outperforms the state-of-the-art ratio of 0.781 from Kurokawa [22]. The time complexity of our FFD-based algorithm is [Formula: see text]. <\/jats:p>","DOI":"10.1142\/s0129054122460066","type":"journal-article","created":{"date-parts":[[2023,1,19]],"date-time":"2023-01-19T02:55:25Z","timestamp":1674096925000},"page":"683-695","source":"Crossref","is-referenced-by-count":0,"title":["Restricted Existence and Approximation Algorithms for PMMS"],"prefix":"10.1142","volume":"36","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5719-1659","authenticated-orcid":false,"given":"Xinru","family":"Guo","sequence":"first","affiliation":[{"name":"Shenzhen Institute of Advanced Technology, Chinese Academy of Sciences, Shenzhen, Guangdong Province, P. R. China"},{"name":"University of Chinese Academy of Sciences, Beijing, 100049, P. R. China"}]},{"given":"Sijia","family":"Dai","sequence":"additional","affiliation":[{"name":"Shenzhen Institute of Advanced Technology, Chinese Academy of Sciences, Shenzhen, Guangdong Province, P. R. China"},{"name":"University of Chinese Academy of Sciences, Beijing, 100049, P. R. China"}]},{"given":"Guichen","family":"Gao","sequence":"additional","affiliation":[{"name":"Peking University, Beijing, P. R. China"}]},{"given":"Ruikang","family":"Ma","sequence":"additional","affiliation":[{"name":"Shenzhen Institute of Advanced Technology, Chinese Academy of Sciences, Shenzhen, Guangdong Province, P. R. China"},{"name":"University of Chinese Academy of Sciences, Beijing, 100049, P. R. China"}]},{"given":"Yicheng","family":"Xu","sequence":"additional","affiliation":[{"name":"Shenzhen Institute of Advanced Technology, Chinese Academy of Sciences, Shenzhen, Guangdong Province, P. R. China"},{"name":"Guangxi Key Laboratory of Cryptography and Information Security (Guilin 541004), Guilin, Guangxi Province, P. R. China"}]},{"given":"Li","family":"Ning","sequence":"additional","affiliation":[{"name":"Shenzhen Institute of Advanced Technology, Chinese Academy of Sciences, Shenzhen, Guangdong Province, P. R. China"}]},{"given":"Jianping","family":"Fan","sequence":"additional","affiliation":[{"name":"Shenzhen Institute of Advanced Technology, Chinese Academy of Sciences, Shenzhen, Guangdong Province, P. R. China"},{"name":"University of Chinese Academy of Sciences, Beijing, 100049, P. R. China"}]}],"member":"219","published-online":{"date-parts":[[2023,1,19]]},"reference":[{"key":"S0129054122460066BIB001","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(87)90055-7"},{"key":"S0129054122460066BIB002","doi-asserted-by":"publisher","DOI":"10.1145\/3147173"},{"key":"S0129054122460066BIB003","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2020.07.006"},{"key":"S0129054122460066BIB004","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.52"},{"key":"S0129054122460066BIB005","doi-asserted-by":"publisher","DOI":"10.1145\/3381525"},{"key":"S0129054122460066BIB006","doi-asserted-by":"publisher","DOI":"10.1145\/3219166.3219176"},{"key":"S0129054122460066BIB007","doi-asserted-by":"publisher","DOI":"10.1007\/s10458-015-9287-3"},{"key":"S0129054122460066BIB008","doi-asserted-by":"publisher","DOI":"10.1086\/664613"},{"key":"S0129054122460066BIB009","doi-asserted-by":"publisher","DOI":"10.1109\/TNSE.2018.2830307"},{"key":"S0129054122460066BIB010","doi-asserted-by":"publisher","DOI":"10.1145\/3328526.3329574"},{"key":"S0129054122460066BIB011","doi-asserted-by":"publisher","DOI":"10.1145\/3355902"},{"key":"S0129054122460066BIB012","doi-asserted-by":"publisher","DOI":"10.1145\/3391403.3399511"},{"key":"S0129054122460066BIB013","doi-asserted-by":"publisher","DOI":"10.1137\/20M1359134"},{"key":"S0129054122460066BIB014","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054110007611"},{"key":"S0129054122460066BIB017","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.164"},{"key":"S0129054122460066BIB018","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74450-4_1"},{"key":"S0129054122460066BIB019","volume":"69","author":"Garg J.","year":"2019","journal-title":"Open Access Series in Informatics"},{"key":"S0129054122460066BIB020","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2021.103547"},{"key":"S0129054122460066BIB021","doi-asserted-by":"publisher","DOI":"10.1145\/3219166.3219238"},{"key":"S0129054122460066BIB023","doi-asserted-by":"publisher","DOI":"10.1145\/3140756"},{"key":"S0129054122460066BIB024","doi-asserted-by":"publisher","DOI":"10.1145\/988772.988792"},{"key":"S0129054122460066BIB025","doi-asserted-by":"publisher","DOI":"10.1137\/19M124397X"},{"key":"S0129054122460066BIB026","doi-asserted-by":"publisher","DOI":"10.1201\/9781439863855"},{"key":"S0129054122460066BIB027","first-page":"101","volume":"16","author":"Steihaus H.","year":"1948","journal-title":"Econometrica"},{"key":"S0129054122460066BIB028","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.02.045"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054122460066","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,22]],"date-time":"2025-07-22T03:43:39Z","timestamp":1753155819000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0129054122460066"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,19]]},"references-count":25,"journal-issue":{"issue":"05","published-print":{"date-parts":[[2025,8]]}},"alternative-id":["10.1142\/S0129054122460066"],"URL":"https:\/\/doi.org\/10.1142\/s0129054122460066","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"type":"print","value":"0129-0541"},{"type":"electronic","value":"1793-6373"}],"subject":[],"published":{"date-parts":[[2023,1,19]]}}}