Karen Aardal教授谈“Topics in discrete optimization: cutting and branching”

luyuanhong

Karen Aardal教授谈“Topics in discrete optimization: cutting and branching”

来源：国家数学与交叉科学中心

2015年11月17日上午, 荷兰代尔夫特理工大学Karen Aardal 教授应国家数学与交叉科学
中心的邀请，作了题为“Topics in discrete optimization: cutting and branching”的
综合报告。数学院副院长、国家数学交叉中心副主任高小山研究员主持报告，并为
Karen Aardal 教授颁发了讲座证书。参加同期中荷双边研讨会的数十位专家学者，以及
来自多所高校的同学参加了报告会。

Karen Aardal教授在报告中首先以最大匹配、最小支撑树等著名组合优化问题为例探讨了
扩张复杂度、简洁表示和多项式可解性之间的关系。随后，她以背包问题为例展示了一些
组合优化的扩展表达可以为寻找整点凸包提供好的分支方向。最后，她以选址问题为例介
绍了对线性规划松弛的强化以获得常数因子的近似。对于这些离散优化中的热点问题，整
个报告既回顾了相关的经典结果，又介绍了最新的重要进展。

作为荷兰代尔夫特理工大学运筹优化方向研究的代表，Karen Aarda教授在报告后就相关
内容，与研究院及中心同领域的师生进行了深入探讨，期待未来有进一步的合作。