题目：Streaming Submodular Maximization under Noises

报告人：徐大川  教授（北京工业大学）

时间：2019年4月22日  下午2:30-3:30

地点：西大楼108

摘要：Motivated by the need for analyzing the rapidly producing data streams, such as images, videos, sensor data, etc, in a timely manner, the study on the streaming algorithms to extract representative information from massive data to maximize some objective function is therefore important and urgent. Most of previous works are assumed under a noise-free environment, while in many realistic applications obtaining the exact function value is hard or computing the function value may cost much, which brings the noisy version. Hence in this paper, we address a more general problem to select a subset of at most $k$ elements from the stream to maximize a noisy set function (not necessarily submodular). To be specific, we cast our problem as the streaming submodular maximization problem with multiplicative and additive noise models. We develop an efficient thresholding streaming algorithm, which is $\frac{1}{k+1}$-approximation for both of noisy models and has a memory independent of data size. In our numerical experiments, we extensively evaluate the effectiveness of our thresholding streaming algorithm on some applications in real data set.

个人简介：徐大川，北京工业大学数理学院，教授，博士生导师。2002年于中国科学院数学与系统科学研究院计算数学与科学工程计算研究所获得博士学位，2004年于中国科学院数学与系统科学研究院应用数学研究所博士后出站。曾访问斯坦福大学，加拿大新布伦瑞克大学，西蒙弗雷泽大学，香港中文大学等。研究兴趣包括：组合优化，近似算法，机器学习与优化，算法博弈论，鲁棒优化，供应链管理等。中国运筹学会数学规划分会副理事长/秘书长，北京运筹学会副理事长，中国运筹学会副秘书长/理事，中国数学会理事。《Applied Mathematics and Computation》、《Asia-Pacific Journal of Operational Research》、《Journal of the Operations Research Society of China》、《Statistics, Optimization and Information Computing》、《运筹与管理》编委，《Algorithmica》、《Journal of Combinatorial Optimization》、《运筹学学报》特约编委。曾获得中国运筹学会青年论文奖一等奖、中国运筹学会运筹新人奖。主持国家自然科学基金六项，国家自然科学基金重点项目子课题一项。在科学出版社出版学术专著《设施选址问题的近似算法》，在Mathematical Programming, Omega，INFORMS Journal on Computing，Algorithmica，Theoretical Computer Science，Journal of Combinatorial Optimization，Journal of Global Optimization，Information Process Letters，Operations Research Letters等发表学术论文100余篇。

邀请人：赵秋兰 老师