2026-07-31T03:21:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24957 2026-02-09T08:02:36Z ddc:004 open_access

Maximizing Social Welfare Among EF1 Allocations at the Presence of Two Types of Agents Ma, Jiaxuan Chen, Yong Chen, Guangting Gong, Mingyang Lin, Guohui Zhang, An Fair allocation utilitarian social welfare envy-free up to one item envy-cycle elimination round robin approximation algorithm We study the fair allocation of indivisible items to n agents to maximize the utilitarian social welfare, where the fairness criterion is envy-free up to one item and there are only two different utility functions shared by the agents. We present a 2-approximation algorithm when the two utility functions are normalized, improving the previous best ratio of 16 √n shown for general normalized utility functions; thus this constant ratio approximation algorithm confirms the APX-completeness in this special case previously shown APX-hard. When there are only three agents, i.e., n = 3, the previous best ratio is 3 shown for general utility functions, and we present an improved and tight 5/3-approximation algorithm when the two utility functions are normalized, and a best possible and tight 2-approximation algorithm when the two utility functions are unnormalized. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jiaxuan Ma and Yong Chen and Guangting Chen and Mingyang Gong and Guohui Lin and An Zhang 2025 Is Part Of LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2025.49 urn:nbn:de:0030-drops-249570 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.49 eng https://creativecommons.org/licenses/by/4.0/legalcode