报告题目： Combinatorial Optimization with Labeling: Algorithms and Complexity 

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

报告时间：4月15号下午 2：30-3：15 

地点：管理楼1418

摘要: Combinatorial optimization is an important topic in the fields of operations research and theoretical computer science, with applications in various areas.  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 each edge of the graph has a label and each label 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 labels used is minimized. We call the later -- MST with labeling, which is apparently a generalization of MST and proved to be NP-complete. For almost all combinatorial problems, we may consider a labeling version of the original problem. Some natural questions arise: “What’s the relationship of the original problem and its labeling version?”, “How can we solve the labeling version of the original problem?”. We shall give some answers to both questions.