报 告 人：胡旭东 研究员（中国科学院数学与系统科学研究院）
报告题目：离散优化 - 从在线算法说起
报告时间：2022年6月1日下午14:30-18:00
报告地点：腾讯会议（会议ID：658-191-245）
主办单位：数学与统计学院、科学技术研究院
报告人简介：
胡旭东，研究员，博士生导师；中国运筹学会名誉理事长。1985年毕业于清华大学，获应用数学专业学士学位，1989年毕业于中国科学院应用数学研究所，获运筹学与控制论专业博士学位。自1989年始，一直在中国科学院从事运筹学的理论研究和教学工作，主要研究方向为组合优化、网络博弈、近似算法。2012年被评为第五届“全国优秀科技工作者”。
报告摘要：
离散优化主要研究求解变量具有离散特征及组合性质，可行解集是有限集或无限可数集的优化问题的理论和算法。经典的离散优化问题包括，图论中的染色问题和运筹学中的调度问题等。当我们考虑如何设计求解这些优化问题的算法的时候，都是假设这些优化问题中的所有变量/参数都已经知道了。然而，在人们处理一些实际问题时，常常会遇到一类问题，它们的变量/参数的具体数值事先并不知道，但是还是需要即时做出决定或者选择。这类问题通常称作在线问题，相应的求解算法称作在线算法。报告人将介绍几个经典离散优化问题的在线模型及其求解算法，以及一个著名的未解难题。