题目：Streaming Facility Location in High Dimension

主讲人：Prof. Shaofeng Jiang

摘要

In Euclidean Uniform Facility Location, the input is a set of clients in R^d and the goal is to place facilities to serve them, so as to minimize the total cost of opening facilities plus connecting the clients. We study the classical setting of dynamic geometric streams, where the clients are presented as a sequence of insertions and deletions of points in the grid [\Delta]^d, and we focus on the high-dimensional regime, where the algorithm's space complexity must be poly(d \log \Delta).

We present a new algorithmic framework, based on importance sampling from the stream, for O(1)-approximation of the optimal cost using only poly(d \log \Delta) space. This framework is easy to implement in two passes and can be "compressed" into one pass under the random-order setting. Our main result, for arbitrary-order streams, computes O(d^{1.5})-approximation in one pass by using the new framework but combining the two passes differently. This improves upon previous algorithms that either need space exponential in d or only guarantee O(d \log^2 \Delta)-approximation, and therefore our algorithms for high-dimensional streams are the first to avoid the O(\log \Delta)-factor in approximation that is inherent to the widely-used quadtree decomposition. Our improvement is achieved by introducing a geometric hashing scheme in streaming that maps points in R^d into buckets of bounded diameter, with the key property that every point set of small-enough diameter is hashed into at most poly(d) distinct buckets.

Based on a joint work with Artur Czumaj, Robert Krauthgamer, Pavel Veselý and Mingwei Yang.

主讲人简介

Dr. Shaofeng Jiang is an assistant professor at the Center on Frontiers of Computing Studies (CFCS), Peking University. He obtained his Ph.D. from the University of Hong Kong. Before he joined PKU, he was a postdoctoral researcher at the Weizmann Institute of Science and an assistant professor at Aalto University. His research interest is generally theoretical computer science, with a focus on algorithms for massive datasets, online algorithms and approximation algorithms.

邀请人：张鹏 教授

时间：2022年8月12日10:00-11:00（星期五上午10:00-11:00）

地点：腾讯会议568 106 386

主办：beat365在线体育官网