12月10日 张国川教授学术报告

报告人：张国川 教授 浙江大学

报告题目I：Revisiting Knapsack Problems

报告时间：2025年12月10日 19:00-19:50

报告地点：5278论坛 301室

摘要：Knapsack is one of the fundamental problems in combinatorial optimization. It aims to select a subset of items, each of which is associated with a weight and a size, such that the total size of the items is upper bounded by a budget, and the total weight is maximized. Knapsack as well as its variants has been extensively studied for decades. There are still quite a few algorithmic issues to be settled for the classical model, while more and more challenging Knapsack-like problems are coming. In this talk, we will briefly introduce our recent work on the old and new Knapsack problems.

报告题目II：A Resupply Scheduling Problem

报告时间：2025年12月10日 20:00-20:50

报告地点：5278论坛 301室

摘要：In this talk, we consider the following periodic scheduling problem. Given n sites and m vehicles. Each site has a capacity and consumes certain amount of goods per day, while each vehicle can carry certain amount of goods and supply one site per day. Our goal is to determine whether there exists a supply schedule so that no site ever exhausts its stock. This problem is a generalization of the well-known pinwheel scheduling problem. We focus on a special case that all the sites have the same capacity and the same demand rate. One can show that Round-Robin works if there is a feasible schedule. However, determining the schedulability is still nontrivial. We present the first polynomial-time algorithm that runs in ��(log ��) time. （Joint work with Yuxiao Ma and Yuchen Mao）

张国川教授：浙江大学教授，中国运筹学会副理事长。1995年毕业于中科院应用数学所，获得运筹学博士学位。曾获德国洪堡基金，在基尔大学和弗莱堡大学合作研究。法国INPG、日本京都大学和加拿大西蒙弗雷泽大学访问教授。研究兴趣包括组合优化近似算法、在线算法和算法机制设计。目前担任Annals of Operations Research, International Journal of Foundations of Computer Science, Journal of Scheduling, Journal of Operations Research Society of China等刊物编委，国际会议New Challenges in Scheduling Theory 组织者之一，ISAAC顾问委员会委员和COCOON指导委员会委员。