报告人简介：

专长和学术成就：算法设计，计算几何，组合优化，及他们在医学图像，治疗规划，及诊断 ，生物 ， 网络与移动计算，大规模集成电路设计 等方面的应用。在这些方向的国际期刊和会议上发表了140余篇论文，大部分出现在国际顶级期刊和会议中。解决了几个长期公开的问题和猜想。推广了一类最基本的几何结构和经典问题。

工作单位及主要简历：于1992年和1995获得中国科技大学，计算机科学本科和硕士学位。于2000年获得美国圣母大学（University of Notre Dame）计算机科学与工程博士学位。同年获美国纽约州立大学（布法罗）计算机科学与工程系助理教授职位，现为该系终身正教授。

1.报告题目: A unified framework for clustering constrained data without locality property

  报告时间：2015年7月10日下午14:00

  报告地点：理工楼555

Abstract：In this paper, we consider a class of constrained clustering problems of points in Rd space, where d could be rather high. A common feature of these problems is that their optimal clusterings no longer have the locality property (due to the additional constraints), which is a key property required by many algorithms for their unconstrained counterparts. To overcome the difficulty caused by the loss of locality, we present in this paper a unified framework, called Peeling-and-Enclosing, to iteratively solve two variants of the constrained clustering problems, constrained k-means clustering (k-CMeans) and constrained k-median clustering (k-CMedian). Our framework generalizes Kumar et al.'s elegant k-means clustering approach [35] from unconstrained data to constrained data, and is based on two standalone geometric techniques, called Simplex Lemma and Weaker Simplex Lemma, for k-CMeans and k-CMedian, respectively. Simplex lemma (or weaker simplex lemma) enables us to efficiently approximate the mean (or median) point of an unknown set of points by searching a small-size grid, independent of the dimensionality of the space, in a simplex (or the surrounding region of a simplex), and thus can be used to handle high dimensional data. With these techniques, our framework generates, in nearly linear time (i.e., O(n(log n)k+1d)), O((log n)k) k-tuple candidates for the k mean or median points, and one of them induces a (1 + ε)-approximation for k-CMeans or k-CMedian, where n is the number of points. Combining this unified framework with a problem-specific selection algorithm (which determines the best k-tuple candidate), we obtain a (1 + ε)-approximation for each of the constrained clustering problems. Our framework improves considerably the best known results for these problems. We expect that our technique will be applicable to other constrained clustering problems without locality.

2. Title: FPTAS for minimizing earth mover's distance underRigid transformations and related problems

  报告时间：2015年7月13日下午14:00

  报告地点：理工楼555

Abstract:In this paper, we consider the problem (denoted as EMDRT) of minimizing theearth mover's distance between two sets of weighted points A and B in a fixed dimensional Rdspace under rigid transformation. EMDRT is an important problem in both theory and applicationsand has received considerable attentions in recent years. Previous research on this problem hasresulted in only constant approximations and it has been an open problem for a long time to achievePTAS solution. In this paper, we present the first FPTAS algorithm for EMDRT. Our algorithmruns roughly in O((nm)d+2(lognm)2d) time (which is close to a lower bound on any PTAS for thisproblem), where n and m are the sizes of A and B, respectively. Our result is based on several newtechniques, such as the Sequential Orthogonal Decomposition (SOD) and Optimum Guided Base(OGB), and can be extended to several related problems, such as the problem of earth mover'sdistance under similarity transformation and the alignment problem, to achieve FPTAS for each ofthem.

3.报告题目: Finding Median Point-Set Using Earth Mover’s Distance

  报告时间：2015年17月21日下午14:00

  报告地点：理工楼555

Abstract：In this paper, we study a prototype learning problem, called Median Point-Set, whose objective is to construct a prototype for a set of given point-sets so as to minimize the total Earth Mover’s Distances(EMD)between the prototype and the point-sets, where EMD between two point-sets is measured under af?ne transformation. For this problem, we present the ?rst purely geometric approach. Comparing to existing graph-based approaches (e.g., median graph, shock graph), our approach has several unique advantages: (1) No encoding and decoding procedures are needed to map between objects and graphs, and therefore avoid errors caused by information losing during the mappings; (2) Staying only in the geometric domain makes our approach computationally more ef?cient and robust to noise. We evaluate the performance of our technique for prototype reconstruction on a random dataset and a benchmark dataset, handwriting Chinese characters. Experiments suggest that our technique considerably outperforms the existing graph-based methods.