报告题目: New bounds on the price of anarchy of selfish bin packing with partial punishment

报告人：鲁习文

报告时间：2025年4月25日8:00——9:00

报告地点：数学楼301

报告摘要: The selfish bin packing with partial punishment is studied in this paper. In this problem, the utility of an item is defined as the load of the bin it is in. Each item plays the role of a selfish agent and wants to maximize its own utility. If an item with size si moves to another bin, it has to pay the partial punishment of αsi , where 0 < α < 1.We prove that the price of anarchy (PoA) of this game is at least 1.6424 for any α ∈ (0, 1). In particular, the PoA of this game is at least 5/3 ≈ 1.6667 for any α ∈ ( 2/5 , 1). Furthermore, we obtain a new upper bound of h(α) ≤ 31/18 ≈ 1.7222 on the PoA.

报告人简介：鲁习文，博士，教授，博导；现任华东理工大学应用数学研究所所长，并兼任中国工业与应用数学学会数学模型专业委员会主任、上海市数学建模竞赛组委会主任等。主要研究方向：排序理论与算法、优化理论与应用、数学建模。先后在荷兰 Eindhoven University of Technology、美国 Lehigh University 与 Georgia State University 和香港理工大学等访问和工作。现担任JOCO、DMAA和运筹学学报等多个学术期刊编委。先后获得上海市自然科学二等奖和市教学成果一等奖等；被评为全国优秀教师、上海市高校优秀青年教师、宝钢优秀教师奖等。