时间： 2014年6月9日16:50-17:30

地点： 学院办公楼310会议室

讲座人：北京工业大学  徐大川教授

主持人：张鹏副教授

讲座内容摘要：

本讲座介绍次模顶点覆盖问题的两个变种，即带线性惩罚的次模顶点覆盖问题和带次模惩罚的次模顶点覆盖问题。对这两个问题，给出了两个原始-对偶近似算法，近似比分别为2和4。若在问题的线性规划松驰的对偶规划上，直接应用原始-对偶方案，并不能够保证对偶上升过程在多项式时间内结束。为了克服这个困难，对两个对偶规划进行了放松，得到了两个稍弱的规划。根据这两个放松的对偶规划，设计了具有上述近似比的原始-对偶近似算法。

讲座人简介：

    徐大川教授，北京工业大学数理学院博士生导师。研究方向为组合优化、近似算法、数学规划、博弈论、供应链管理。担任中国运筹学会理事，中国运筹学会数学规划分会副理事长、秘书长，北京运筹学会常务理事。主持多项国家自然科学基金和北京市自然科学基金项目。在科学出版社出版学术专著《设施选址问题的近似算法》，担任运筹与管理、运筹学学报、Applied Mathematics and Computation、Asia-Pacific Journal of Operational Research等期刊的编委或特约编委。在Omega、INFORMS Journal on Computing、Algorithmica、TCS、JOCO、ORL、JGO、IPL、中国科学、数学学报、数学进展、运筹学学报等刊物上发表学术论文80余篇。