题目：Combinatorial Optimization with Coloring

报告人：王卫   教授（西安交通大学）

时间：2019年4月19日 上午9:00-10:00

地点：西大楼108

摘要: Combinatorial optimization is an important topic in the fields of operations research and theoretical computer science, with applications in many areas including artificial intelligence, machine learning, auction theory, and software engineering. In this talk, we consider an invariant (a generalization) of a wide class of combinatorial problems. To give just a simple example, consider the classical minimum spanning tree (MST) problem, in which we are given a connected graph with edge weights, the goal is to find a spanning tree with minimum total weight. Further, if the edges of the graph are colored and each color has a weight. Then, instead of minimizing the total weight of edges, we want to find a spanning tree such that the total weight of different colors used is minimized. We call the later -- MST with coloring, which is apparently a generalization of MST and proved to be NP-complete. For almost all combinatorial problems, we may consider a coloring version of the original problem. Some natural questions arise: “What’s the relationship of the original problem and its coloring version?”, “How can we solve the coloring version of the original problem?”. We shall give some answers to both questions.

个人简历：王卫，西安交通大学教授、博士生导师。1991年在浙江大学获学士学位，分别于1994年及2006年在西安交通大学获硕士及博士学位。主要研究领域为代数图论与组合最优化。在图谱理论的研究中对图的广义谱刻画问题做出了一些原创性的工作，在组合优化领域中对一些NP-困难组合优化问题设计出了一些好的近似算法。目前在J. Combin. Theory, Ser B, European J. Combin., 以及IEEE/ACM Transactions系列等刊物上发表研究论文60余篇。主持完成国家自然科学基金面上项目两项。

邀请人：赵秋兰 老师