报告时间：2026年11月18日 14:00开始

报 告 人：陈林，浙江大学百人计划研究员

报告地点：9-218

报告题目：多维稠密子集和与整数规划

报告摘要：研究了多维稠密子集和问题。设$A$为$d$维超长方体$[0,N_1] \times \cdots \times [0,N_d]$中的整点，$\Phi$为超长方体的体积。设$\mathcal{P}(A)$为以$A$中的点作为生成元(generator)构成的奇诺多面体(zonotope)，$\mathcal{S}(A)$为$A$的所有子集和。证明了当$A$满足稠密性(density)与分离性(spreadness)时，$\mathcal{S}(A)$几乎包含了$\mathcal{P}(A)$中的所有整点。这里稠密指的是$|A|$至少达到$\sqrt{\Phi}$的量级，而分离指的是$A$中绝大部分的整点不能落在某个非平凡的格(lattice)上。

在本文之前，这一结论仅对$d=1$成立[Lev'03]。我们将这一加性组合的结果系统推广到了多维。

利用上述组合结构，我们得到了如下算法结果：针对多维稠密子集和问题的几乎线性时间算法。在本文之前，仅针对$d=1$存在这样的算法[Galil \& Margalit '91][Bringmann\& Wellnitz '21]. 进一步拓展这一技术，我们将0-1整数规划的运行时间从$\Delta^{d^2+d} d^{O(d^2)} poly(|I|)$ [Eisenbrand & Weismantel '24] 改进到了$O_{\eps,d}(\Delta^{2d+\eps}) poly(|I|)$, 其中$\Delta$为约束矩阵绝对值最大元的绝对值。

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