地点：数计学院6号楼309室

报告内容简介：

For various types of contemporary networks resulted by information communication technology advancement, with their rapidly increasing size, topological complexity and application variety, network survivability is attracting more and more attention nowadays. How to minimize resource (bandwidth) usage while ensuring a guaranteed network survivability is an interesting problem of both theoretical significance and application value, which is called the survivable network design problem in the general setting. It is especially important for the emerging cloud computing, datacenter networks and the next generation Internet that have a high degree of interconnection complexity and fault dynamicity. A practical appearance of  this problem that arises in a wide range of applications is the so-called Steiner network problem that generalizes the classical Steiner tree  (1-connected) problem  and assumes a uniform connectivity (survivability) across the subset of nodes (terminals) concerned. W hen this subset spans to the whole network, the Steiner network problem reduces to the connected spanning subgraph problem which was shown NP-hard. Numerous efforts have been made in searching for effective approximation solutions for these problems in the past decades. In this talk, I will first provide an overview on the existing solutions to the above three problems. I will then introduce our recent work on constructing a 2-connected Steiner network that has an approximation ratio of 2 to the optimal (minimum cost) solution through progressive improvement on a set of disjoint shortest path pairs incident with each terminal. Next I will show how to compute a 6-approximation augmentation on the 2-connected Steiner network to achieve connectivity 3 by constructing a minimum-cost in-arborescence in the directed complete graph with vertices being all terminals and each edge weight the shortest path distance between the end vertices. Finally I will conclude the talk by presenting some open problems for future research.

报告人简介:

Dr. Hong Shen is Professor (Chair) of Computer Science in the University of Adelaide, Australia, and currently also a \"1000 People Plan\" professor in Sun Yat-sen University, China. With main research interests in parallel and distributed computing, algorithms, data mining, privacy preserving computing, high performance networks and multimedia systems, he has published more than 300 papers including over 100 papers in international journals such as a variety of IEEE and ACM transactions. Prof. Shen received many honours/awards including China National “1000 People Plan” Expert, Chinese Academy of Sciences “Hundred Talents”, National Education Commission Science and Technology Progress Award, and Chinese Academy of Sciences Natural Sciences Award. He served on the editorial board of numerous international journals.