报告题目:组合优化– 模型、理论、算法
报告人:胡晓东研究员
时间:7月21日上午
报告摘要:
组合优化是上个世纪五、六十年代逐渐形成的运筹学和理论计算机科学的一个重要交叉分支。它主要研究如何设计快速算法,使其可以在给定的有限集合的所有满足特定条件的子集中,以某种目标找出一个最优子集。一般这些问题的描述都非常简单,并且有非常强的应用背景,但求得其最优解却是非常困难的。其主要原因是枚举法考虑所有可能的情况,故需要极长的运行时间,以致根本不可能用现有计算机在可接受的时间内完成;而启发式算法尽管运行时间短,但是却不能保证一定可以找到最优解。正是这些问题的应用广泛性和计算复杂性,激发起了人们对组合优化的强烈兴趣,使其成为了一个最年轻和最活跃的研究领域。
报告人将通过来源于实际生活中的若干经典组合优化问题,展示求解这些问题的数学模型、复杂性理论、算法设计与分析方法。
胡晓东简介:现任中国科学院数学与系统科学研究院研究员,院长业务助理,中国运筹学会理事长。1985年毕业于清华大学,获应用数学专业学士学位,1989年毕业于中国科学院应用数学研究所,获运筹与控制论专业博士学位。自1989年始,一直在中中国科学院从事运筹学的理论研究和教学工作,主要研究方向为组合优化、网络博弈、近似算法。2012年被评为第五届“全国优秀科技工作者”。