3月27日下午，应数学与统计学院与科技处邀请，山东大学计算机学院张鹏副教授、山东建筑大学计算机学院张冬梅副教授和北京工业大学数理学院徐大川教授于长清湖校区C236教室分别作了题为《标签s-t割问题的一个简单且好的近似算法》、《A local search approximation algorithm for a sum of squares k-facility location problem》和《设施选址问题的近似算法》的学术报告，数学与统计学院部分教师、研究生参加了此次学术报告。
在本次报告会上，首先，张鹏副教授风趣幽默地为在场的师生讲述了标签s-t割问题的背景，并给出这个NP-Hard问题的三种近似算法，分别叙述了贪心算法，线性规划舍入算法和张鹏教授经过自身努力所研究出来的第三种通过去掉最长路，进而寻找最小割的又简单又好的算法。接着，张冬梅副教授在讲座中首先介绍了分类和聚类的区别，概括的说分类就是有标签，但是聚类是提前不知道有哪些标签，需要我们给出标签的描述。然后张冬梅副教授又介绍了K-means是聚类中用的比较多的算法，并讲解了K-means算法在划分欧氏空间中数据点的具体应用。最后，徐大川教授针对设施选址问题进行深入浅出的分析。其是运筹学和理论计算机科学中的经典问题之一，有着广泛的研究背景。徐老师从同学们容易理解的线性规划入手，以雾霾检测仪、垃圾站、医院、仓库、代理服务器的选址或配置问题为出发点介绍了选址问题的重要性。由于设施选址问题是经典的NP.困难问题。在P≠NP的著名猜想成立的条件下无法找到最优解。从而引出近似算法是处理NP.困难问题的重要方法之一。对于极小化问题而言，如果对任意实例，算法A所解的费用不超过该实例最优质的值，则称算法A为近似算法。通过此次报告会，大家都对近似算法有了更进一步的了解，开阔了眼界，了解了更多的有关运筹和控制的知识，鼓舞了大家对科研的热情。
徐大川，北京工业大学数理学院教授，博士生导师，科研副院长。2002年于中国科学院数学与系统科学研究院计算数学与科学工程计算研究所获得博士学位，2004年于中国科学院数学与系统科学研究院应用数学研究所博士后出站。曾访问斯坦福大学，加拿大新布伦瑞克大学，西蒙弗雷泽大学，香港中文大学等。研究兴趣包括：组合优化，近似算法，算法博弈论，鲁棒优化，供应链管理等。中国运筹学会数学规划分会副理事长/秘书长，北京运筹学会副理事长，中国运筹学会理事，中国数学会理事。《Asia-Pacific Journal of Operational Research》、《Applied Mathematics and Computation》、《运筹与管理》编委，《Algorithmica》、《Journal of Combinatorial Optimization》、《运筹学学报》特约编委。
张鹏，山东大学计算机学院副教授。2007年7月于中科院软件所取得博士学位。长期以来从事组合优化和近似算法的研究。在Algorithmica、ToCS、TCS、DAM等主流国际期刊，以及LATIN、ISAAC、COCOON等主流国际会议发表论文40多篇，其中以第一作者、通讯作者发表SCI索引论文14篇。主持国家自然科学基金面上项目两项。
张冬梅，现为山东建筑大学计算机学院副教授。2012年获山东大学计算机应用技术专业理学博士。主要研究兴趣为机器学习和信息检索，特别是文本情感分析。
编辑：陈佳惠
审核：崔翠翠
Copyright 山东师范大学 党委研究生工作部
