北京科学与工程计算研究院学术报告之六十五

报告人/Speaker: 聂嘉明 (中山大学数学学院(珠海))


报告题目/Title: Approximation algorithms for a two-phase knapsack problem


时间/Date & Time: June 19, 2018, 14:00—15:00


地点/Location: 理科楼M842报告厅


报告摘要/Abstract:In this talk, we will present a natural generalization of the knapsack problem and the multiple knapsack problem, which has two phases of packing decisions. In this problem, we have a set of items, several small knapsacks called boxes, and a large knapsack called container. Each item has a size and profit, each box has a size and the container has a capacity. The first phase is to select some items to pack into the boxes, and the second phase is to select the boxes (each includes some packed items) to pack into the container. The total profit of the problem is determined by the items that are selected and packed into the container within some packed box, and the objective is to maximize the total profit. This problem is motivated by various practical applications, e.g., in logistics. It is a generalization of the multiple knapsack problem, and hence is strongly NP-hard. We mainly propose three approximation algorithms for it. Particularly, the first one is a $\frac{1}{4}$-approximation algorithm based on its linear programming relaxation; the second one is based on applying the algorithms for the multiple knapsack problem and the knapsack problem, and has an approximation ratio $\frac{1}{3} - \epsilon$ for any small enough $\epsilon>0$. We finally provide a polynomial time approximation scheme for this problem.


报告人简介/About the speaker:  

聂嘉明, 2017年毕业于清华大学数学科学系,获得理学博士学位。现为中山大学数学学院(珠海)副研究员,主要研究方向为组合优化的近似算法和计算复杂性等。曾分别于2013年和2016年到比时鲁汶大学决策科学与信息管理系和美国明尼苏达大学工业与系统工程系交流访学。研究论文发表在期刊European Journal of Operational Research, Theoretical Computer Science, Journal of Global Optimization, Journal of Combinatorial Optimization, Transportation Research Part B: Methodological和会议COCOON等, 曾获得北京运筹学会2016 青年优秀论文二等奖、博士研究生国家奖学金等。