一本道

“七秩工大，学术领航”——70周年校庆系列学术讲座

报告题目：A (3/2-ε)-approximation Algorithm for the Bottleneck Multiple Knapsack Problem

报  告 人： 陈林 (浙江大学)

报告时间： 2026年5月27号 17：35-18：20

报告地点： 莲花街校区惟德楼315会议室

报告摘要：

The bottleneck multiple knapsack problem is one of the classic combinatorial optimization problems, which is defined as follows. Given a set of items and a set of knapsacks, each item has a profit and a weight, and all the knapsacks have identical capacity. Items are selected and packed into the knapsacks subject to the capacity constraint. The goal is to maximize the minimum profit among all the knapsacks. Our main result is a (3/2-ε) -approximation algorithm with a running time of \text{Poly}(|I|) + n^{2^{O\left(\frac{1}{\varepsilon^2}\right)}} where |I| is the size of any input instance and n is the number of the items. The approximation ratio almost matches the inapproximability of (3/2-ε) by Caprara, Kellerer and Pferschy [SIAM Journal on Optimization, 2000].

报告人简介：陈林博士，现为浙江大学百人计划研究员，之前在德克萨斯理工大学任助理教授。2013年毕业于浙江大学。获得2024年运筹学会青年科技奖，现主持中国自然科学基金海外优青项目和1项面上项目。主要研究方向为组合优化，研究课题包括子集和，背包，排序，以及分块结构整数规划等问题的近似算法和参数算法。在SODA, STOC, FOCS等理论计算顶级会议，以及SIAM Journal on Computing, Mathematical Programming, Mathematics of Operations Research等权威期刊上发表数十篇文章。

一本道

2026年5月25日