报告主题：离散优化 - 从在线算法说起

报 告 人：胡旭东 研究员（中国科学院数学与系统科学研究院）

报告时间：2022年4月1日（周五） 9:15

参会方式：腾讯会议

会议ID：924-840-712

邀请人：康丽英

主办部门：理学院数学系

报告摘要：离散优化主要研究求解变量具有离散特征及组合性质，可行解集是有限集或无限可数集的优化问题的理论和算法。经典的离散优化问题包括，图论中的染色问题和运筹学中的调度问题等。当我们考虑如何设计求解这些优化问题的算法的时候，都是假设这些优化问题中的所有变量/参数都已经知道了。然而，在人们处理一些实际问题时，常常会遇到一类问题，它们的变量/参数的具体数值事先并不知道，但是还是需要即时做出决定或者选择。这类问题通常称作在线问题，相应的求解算法称作在线算法。报告人将介绍几个经典离散优化问题的在线模型及其求解算法，以及一个著名的未解难题。