报告时间：2023年06月19日14：00开始
报 告 人：陈林（美国德州理工大学 教授）
报告地点：9-401
报告题目：负载均衡问题的次指数时间近似方案
报告摘要：我们考察经典的调度问题。给定 m 台平型机与 n 个工件，对任意常数$q>1$，我们需要将工件分配到机器上使得目标函数$\sum_{i=1}^m C_i^q$最小，其中$C_i$是机器$i$的负载，即机器$i$上所有工件的处理时间之和。这是一个经典的强 NP 困难问题。在比较自然的复杂性假设下，强NP困难问题的$ (1+\epsilon)$近似算法 (即近似方案)不能是$1/\epsilon$的多项式。目前已知的强NP困难问题，其近似方案的运行时间至少为$2^{\Omega (1/\epsilon)}+n^{\OO (1)}$。对上述负载均衡问题，我们首次得到了次指数时间的近似方案，特别的，其运行时间为$2^{\tilde{\OO} (\sqrt{1/\epsilon})}+n^{\OO(1)}$。我们同时证明了该运行时间在指数时间猜想 (Exponential time hypothesis)下是几乎最优的。
报告人简介：
陈林现为美国德克萨斯理工大学教授，研究方向为组合优化问题的近似算法与参数算法，重点从事分块结构整数规划，调度 (scheduling)，装箱等问题的算法研究，在SODA, SPAA, ICALP，ESA等国际顶级会议，SICOMP, Math Program，JCSS等顶级期刊发表过二十余篇文章。现主持美国国家自然科学基金一项。
