报告时间：2025年5月25日 18:30开始
报 告 人：陈永（教授，博士生导师，杭州电子科技大学）
报告地点：9-102
报告题目：Maximizing social welfare among EF1 allocations at the presence of two types of agents
报告摘要: 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. 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 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.
报告人简介：陈永，教授，博导，杭州电子科技大学理学院数学系。现任中国运筹学会排序分会理事、中国工业与应用数学学会数学模型专业委员会委员。研究兴趣为算法理论，主要针对组合优化、图论与网络优化和排序理论进行算法设计与分析。已发表高水平SCI期刊论文和算法理论国际会议论文40多篇，主持国家自然科学基金面上项目2项，并参与多项省部级以上科研项目。曾先后访问加拿大阿尔伯塔大学、东京电机大学等，与国内外知名学者开展合作研究。
