报告题目：On the Connectivity Preserving Minimum Cut Problem
报告人：Jinhui Xu (徐金辉) 教授（State University of New York at Buffalo）
时间：2016年7月21日上午10:30-11:30
地点：天赐庄校区理工楼633室
报告摘要：In this paper, we study a generalization of the classical minimum cut problem, called Connectivity Preserving Minimum Cut (CPMC) problem, which seeks a minimum cut to separate a pair (or pairs) of source and destination nodes and meanwhile ensure the connectivity between the source and its partner node(s). For this problem, we consider two variants, connectivity preserving minimum node cut (CPMNC) and connectivity preserving minimum edge cut (CPMEC). For CPMNC, we show that it cannot be approximated within α logn for some constant α unless P = NP, and cannot be approximated within any poly(logn) unless NP has quasi-polynomial time algorithms. The hardness results hold even for graphs with unit weight and bipartite graphs. For CPMEC, we show that it is in P for planar graphs.
报告人介绍：Dr. Xu is currently a professor of Computer Science and Engineering at the University at Buffalo (the State University of New York). He received his B.S. and M.S. degrees in Computer Science from the University of Science and Technology of China (USTC), and his Ph.D. degree in Computer Science and Engineering from the University of Notre Dame in 2000. Dr. Xu's research interest lies in the fields of Algorithms, Computational Geometry, Combinatorial Optimization, Machine Learning, and their applications in several applied areas. His recent research has focused on the development of geometric algorithms and machine learning methods for problems arising in medicine (medical imaging and interventional procedures for intracranial aneurysms), biology (determining the spatial patterns of chromosome organization inside the cell nucleus, as well as their alterations in cell differentiation, cell cycle, and progression of diseases such as cancer), networking, and 3D printing. Dr. Xu's research has been supported by National Science Foundation (NSF), National Institute of Health (NIH), NYSTAR, IBM, and University at Buffalo. He is a recipient of UB Exceptional Scholar: Sustained Achievement Award (2015), SEAS Senior Researcher of the Year Award (2015), the NSF CAREER Award (2005) and the IBM Faculty Partnership Award (2001).