学术报告
Efficient Approximations for the Online Dispersion Problem-Jing Chen (Assistant Professor, Stony Brook University)
题目：Efficient Approximations for the Online Dispersion Problem
报告人: Jing Chen (Assistant Professor, Stony Brook University)
报告人简介：
Jing Chen is an Assistant Professor in the Department of Computer Science at Stony Brook University. She is also an Affiliated Assistant Professor in the Department of Economics and an Affiliated Member of the Stony Brook Center for Game Theory. Her major reseach interests are game theory and mechanism design. She is also interested in algorithms, block chains, artificial intelligence and logic. Jing received her B.E. and M.E. in Computer Science from Tsinghua University, and her PhD in Computer Science from MIT. Before joining Stony Brook in 2013, she did a one-year postdoc at the School of Mathematics in the Institute for Advanced Study. She has received the NSF CAREER Award for her research on game theory and mechanism design.
6月27日（周二）下午2:00-3:00,
地点：首都师大新教二楼827 教室
Abstract:
The dispersion problem has been widely studied in computational geometry and facility location, and is closely related to the packing problem. The goal is to locate n points (e.g., facilities or persons) in a k-dimensional polytope, so that they are far away from each other and from the boundary of the polytope. In many real-world scenarios however, the points arrive and depart at different times, and decisions must be made without knowing future events. Therefore we study, for the first time in the literature, the online dispersion problem in Euclidean space.
For two natural objectives, the all-time worst-case (ATWC) problem and the cumulative distance (CD) problem, we construct efficient online competitive algorithms and prove corresponding lower-bounds for the competitive ratios. For the online ATWC problem on a segment, we construct a deterministic polynomial-time algorithm which is (2ln(2)+epsilon)-competitive, where epsilon>0 can be arbitrarily small and the algorithm's running time is polynomial in 1/epsilon. We show this algorithm is actually optimal. For the same problem in a square, we provide a 1.591-competitive algorithm and a 1.183 lower-bound. Furthermore, for arbitrary k-dimensional polytopes with k greater than or equal to 2, we provide a 2/(1-epsilon)-competitive algorithm and a 7/6 lower-bound. Interestingly, for the offline CD problem in arbitrary k-dimensional polytopes, we provide a polynomial-time black-box reduction to the online ATWC problem, and the resulting competitive ratio increases by a factor of at most 2. Our techniques also apply to online dispersion problems with different boundary conditions.
欢迎研究生积极参加！
