报告题目：New Streaming Algorithms for High Dimensional EMD and MST

演讲摘要：We study streaming algorithms for two fundamental geometric problems: computing the cost of an Minimum Spanning Tree (MST) of an n-point set from [m]^d, and computing the Earth Mover Distance (EMD) between two multi-sets from [m]^d of size n. We consider the turnstile model, where points can be added and removed. We give a one-pass streaming algorithm for MST and a two-pass streaming algorithm for EMD, both achieving an approximation factor of O(log n) and using polylog(n,d,m)-space only. Our algorithms are based on an improved analysis of a recursive space partitioning method known as the Quadtree. Specifically, we show that the Quadtree achieves an O(log n) approximation for both EMD and MST, improving on the previous best bounds of O(min(log n, log(md)) log n).

讲者简介：陈汐，哥伦比亚大学计算机系的副教授。于2007获得清华大学博士学位。在加入哥伦比亚大学之前，是普林斯顿大学和南加州大学高级研究所的博士后研究员。他的研究兴趣在于算法博弈论和复杂性理论。