{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T17:12:20Z","timestamp":1775841140909,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":41,"publisher":"ACM","funder":[{"name":"Hong Kong SAR Research Grants Council","award":["PolyU 15224823"],"award-info":[{"award-number":["PolyU 15224823"]}]},{"name":"Guangdong Basic and Applied Basic Research Foundation","award":["2024A1515011524"],"award-info":[{"award-number":["2024A1515011524"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,4,13]]},"DOI":"10.1145\/3774904.3792590","type":"proceedings-article","created":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T21:54:34Z","timestamp":1775771674000},"page":"339-350","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Efficient and Fair Allocation on Graphs: From Orientation to Position-Aware Valuations"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7500-8355","authenticated-orcid":false,"given":"Bo","family":"Li","sequence":"first","affiliation":[{"name":"Department of Computing, The Hong Kong Polytechnic University, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1464-1979","authenticated-orcid":false,"given":"Ankang","family":"Sun","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology, Shandong University, Qingdao, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-8442-3708","authenticated-orcid":false,"given":"Shiji","family":"Xing","sequence":"additional","affiliation":[{"name":"Department of Computing, The Hong Kong Polytechnic University, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,4,12]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.65109\/ESDK4357"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.4"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Hannaneh Akrami Kurt Mehlhorn Masoud Seddighin and Golnoosh Shahkarami. 2023. Randomized and Deterministic Maximin-share Approximations for Fractionally Subadditive Valuations. In NeurIPS.","DOI":"10.52202\/075280-2565"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2023.103965"},{"key":"e_1_3_2_1_5_1","first-page":"1268","article-title":"Pushing the Frontier on Approximate EFX Allocations","author":"Amanatidis Georgios","year":"2024","unstructured":"Georgios Amanatidis, Aris Filos-Ratsikas, and Alkmini Sgouritsa. 2024. Pushing the Frontier on Approximate EFX Allocations. In EC. ACM, 1268-1286.","journal-title":"EC. ACM"},{"key":"e_1_3_2_1_6_1","first-page":"242","article-title":"Guaranteeing Envy-Freeness under Generalized Assignment Constraints","author":"Barman Siddharth","year":"2023","unstructured":"Siddharth Barman, Arindam Khan, Sudarshan Shyam, and K. V. N. Sreenivas. 2023. Guaranteeing Envy-Freeness under Generalized Assignment Constraints. In EC. ACM, 242-269.","journal-title":"EC. ACM"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3381525"},{"key":"e_1_3_2_1_8_1","volume-title":"Scott","author":"Berman Piotr","year":"2003","unstructured":"Piotr Berman, Marek Karpinski, and Alex D. Scott. 2003. Approximation Hardness of Short Symmetric Instances of MAX-3SAT. Electron. Colloquium Comput. Complex., Vol. TR03-049 (2003)."},{"key":"e_1_3_2_1_9_1","first-page":"1","article-title":"On Approximate Envy-Freeness for Indivisible Chores and Mixed Resources. In APPROX\/RANDOM (LIPIcs, Vol. 207)","volume":"1","author":"Bhaskar Umang","year":"2021","unstructured":"Umang Bhaskar, A. R. Sricharan, and Rohit Vaish. 2021. On Approximate Envy-Freeness for Indivisible Chores and Mixed Resources. In APPROX\/RANDOM (LIPIcs, Vol. 207). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 1:1-1:23.","journal-title":"Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2021.11.006"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2018\/13"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2017\/20"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1086\/664613"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3355902"},{"key":"e_1_3_2_1_15_1","first-page":"473","article-title":"Fair allocation in graphs","author":"Christodoulou George","year":"2023","unstructured":"George Christodoulou, Amos Fiat, Elias Koutsoupias, and Alkmini Sgouritsa. 2023. Fair allocation in graphs. In EC. ACM, 473-488.","journal-title":"EC. ACM"},{"key":"e_1_3_2_1_16_1","volume-title":"Exact and approximate maximin share allocations in multi-graphs. CoRR","author":"Christodoulou George","year":"2031","unstructured":"George Christodoulou and Symeon Mastrakoulis. 2025. Exact and approximate maximin share allocations in multi-graphs. CoRR, Vol. abs\/2506.20317 (2025)."},{"key":"e_1_3_2_1_17_1","first-page":"56","volume-title":"IJCAI. ijcai.org","author":"Deligkas Argyrios","unstructured":"Argyrios Deligkas, Eduard Eiben, Tiger-Lily Goldsmith, and Viktoriia Korchemna. 2025. EF1 and EFX Orientations. In IJCAI. ijcai.org, 56-63."},{"key":"e_1_3_2_1_18_1","first-page":"55","article-title":"Fair Division of Chores with Budget Constraints. In SAGT (Lecture Notes in Computer Science, Vol. 15156)","author":"Elkind Edith","year":"2024","unstructured":"Edith Elkind, Ayumi Igarashi, and Nicholas Teh. 2024. Fair Division of Chores with Budget Constraints. In SAGT (Lecture Notes in Computer Science, Vol. 15156). Springer, 55-71.","journal-title":"Springer"},{"key":"e_1_3_2_1_19_1","volume-title":"Johnson","author":"Garey M. R.","year":"1979","unstructured":"M. R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman."},{"key":"e_1_3_2_1_20_1","volume-title":"Masoud Seddighin, Saeed Seddighin, and Hadi Yami.","author":"Ghodsi Mohammad","year":"2018","unstructured":"Mohammad Ghodsi, Mohammad Taghi Hajiaghayi, Masoud Seddighin, Saeed Seddighin, and Hadi Yami. 2018. Fair Allocation of Indivisible Goods: Improvements and Generalizations. In EC. ACM, 539-556."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2021.103633"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.3233\/FAIA251259"},{"key":"e_1_3_2_1_23_1","first-page":"630","article-title":"An Algorithmic Framework for Approximating Maximin Share Allocation of Chores","author":"Huang Xin","year":"2021","unstructured":"Xin Huang and Pinyan Lu. 2021. An Algorithmic Framework for Approximating Maximin Share Allocation of Chores. In EC. ACM, 630-631.","journal-title":"EC. ACM"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Xin Huang and Erel Segal-Halevi. 2023. A Reduction from Chores Allocation to Job Scheduling. In EC. ACM 908.","DOI":"10.1145\/3580507.3597676"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3727149"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10458-021-09537-3"},{"key":"e_1_3_2_1_27_1","first-page":"188","article-title":"Maximin Shares Under Cardinality Constraints. In EUMAS (Lecture Notes in Computer Science, Vol. 13442)","author":"Hummel Halvard","year":"2022","unstructured":"Halvard Hummel and Magnus Lie Hetland. 2022b. Maximin Shares Under Cardinality Constraints. In EUMAS (Lecture Notes in Computer Science, Vol. 13442). Springer, 188-206.","journal-title":"Springer"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v37i5.25705"},{"key":"e_1_3_2_1_29_1","volume-title":"Improved Approximate EFX Guarantees for Multigraphs. CoRR","author":"Kaviani Alireza","year":"2025","unstructured":"Alireza Kaviani, Alireza Keshavarz, Masoud Seddighin, and AmirMohammad Shahrezaei. 2025. Improved Approximate EFX Guarantees for Multigraphs. CoRR, Vol. abs\/2506.09288 (2025)."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.65109\/ZMTR6961"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3140756"},{"key":"e_1_3_2_1_32_1","first-page":"21744","article-title":"Fair Scheduling for Time-dependent Resources","author":"Li Bo","year":"2021","unstructured":"Bo Li, Minming Li, and Ruilong Zhang. 2021. Fair Scheduling for Time-dependent Resources. In NeurIPS. 21744-21756.","journal-title":"NeurIPS."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"crossref","unstructured":"Bo Li Fangxiao Wang and Yu Zhou. 2023. Fair Allocation of Indivisible Chores: Beyond Additive Costs. In NeurIPS.","DOI":"10.52202\/075280-2368"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3434410"},{"key":"e_1_3_2_1_35_1","first-page":"125","article-title":"On approximately fair allocations of indivisible goods","author":"Lipton Richard J.","year":"2004","unstructured":"Richard J. Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi. 2004. On approximately fair allocations of indivisible goods. In EC. ACM, 125-131.","journal-title":"EC. ACM"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1146\/annurev-economics-080218-025559"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3505156.3505162"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"crossref","unstructured":"Xiaowei Wu Bo Li and Jiarui Gan. 2025. Approximate envy-freeness in indivisible resource allocation with budget constraints. Inf. Comput. (2025) 105264.","DOI":"10.1016\/j.ic.2024.105264"},{"key":"e_1_3_2_1_39_1","first-page":"235","article-title":"Higher-Order Matching in the Linear Lambda Calculus in the Absence of Constants Is NP-Complete. In RTA (Lecture Notes in Computer Science, Vol. 3467)","author":"Yoshinaka Ryo","year":"2005","unstructured":"Ryo Yoshinaka. 2005. Higher-Order Matching in the Linear Lambda Calculus in the Absence of Constants Is NP-Complete. In RTA (Lecture Notes in Computer Science, Vol. 3467). Springer, 235-249.","journal-title":"Springer"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.65109\/NHSQ9821"},{"key":"e_1_3_2_1_41_1","unstructured":"Yu Zhou Tianze Wei Minming Li and Bo Li. 2024. A Complete Landscape of EFX Allocations on Graphs: Goods Chores and Mixed Manna. In IJCAI. ijcai.org 3049-3056."}],"event":{"name":"WWW '26: The ACM Web Conference 2026","location":"Dubai United Arab Emirates","sponsor":["SIGWEB ACM Special Interest Group on Hypertext, Hypermedia, and Web"]},"container-title":["Proceedings of the ACM Web Conference 2026"],"original-title":[],"deposited":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T16:27:14Z","timestamp":1775838434000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3774904.3792590"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,12]]},"references-count":41,"alternative-id":["10.1145\/3774904.3792590","10.1145\/3774904"],"URL":"https:\/\/doi.org\/10.1145\/3774904.3792590","relation":{},"subject":[],"published":{"date-parts":[[2026,4,12]]},"assertion":[{"value":"2026-04-12","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}