应数学与统计学院张和平教授和徐守军教授邀请，西安交通大学数学与统计学院王卫教授将于2021年7月2日访问我校并作学术报告。

报 告：Minimum Non-submodular Cover Problem with Applications

时 间：7月2日上午10:00

地 点：理工楼631

腾讯会议号：839 925 742 密码：0702

摘要：Minimum Submodular Cover problem often occurs naturally in the context of combinatorial optimization. It is well-known that the greedy algorithm achieves an H(δ)-approximation guarantee for an integer-valued polymatroid potential function f, where δ is the maximum value of f over all singletons and H(δ) is the δ-th harmonic number. In this paper, we extend the setting into the non-submodular potential functions and investigate Minimum Non-submodular Cover problem with integer-valued and fraction-valued potential functions respectively, yielding similar performance results. In addition, we address several real-world applications which can be formulated as Minimum Non-submodular Cover problem.

欢迎广大师生参加！

报告人简介

王卫，西安交通大学教授、博士生导师。主要研究领域为代数图论与组合最优化。在图谱理论的研究中对图的广义谱刻画问题做出了一些原创性的工作，给出了图广义谱刻画的一个简洁的算术条件，证明了具有广义谱唯一性的多重图具有正的密度。在组合优化领域中对一些NP-困难组合优化问题设计出了一些好的近似算法。目前在J. Combin. Theory, Ser B, European J. Combinatorics, 以及IEEE/ACM Transactions系列等刊物上发表研究论文60余篇。主持（完成）国家自然科学基金面上项目两项。

甘肃应用数学中心

萃英学院

甘肃省高校应用数学与复杂系统省级重点实验室

数学与统计学院

2021年6月30日