Today, we had the honor to host excellent talks by two outstanding researchers. Prof. Dr. Dachuan Xu [徐大川] from the School of Mathematics and Physics [北京工业大学数理学院] of the Beijing University of Technology (BJUT) [北京工业大学] presented his work on "Streaming Submodular Maximization under Noise." Prof. Dr. Xiaoyan Zhang [张晓岩] from the School of Mathematical Sciences [南京师范大学数学科学学院] of the Nanjing Normal University (NNU) [南京市仙林大学] gave a talk on his results on the "Max-3-Cut with Limited Unbalance and Application via Complex Semidefinite Programming." These two talks were a highlight for our team and colloquium and were followed by inspiring discussions. We want to thank again both speakers for their visit and their presentations.
Prof. Dr. Dachuan Xu: Streaming Submodular Maximization under Noise
Talk Abstract
There is an ever-growing need for analyzing data streams such as images, videos, or sensor data, in a timely manner. Due to technological advances, such streams steadily grew in volume and throughput over the past years. Thus, the study on the streaming algorithms to extract representative information as a function of the massive data to maximize some objective function is important and urgent. Most of the previous works assume a noise-free environment. I many realistic applications obtaining exact function values is hard or computing such values may cost much. We therefore consider a noisy version of the problem. We address a more general problem to select a subset of at most k elements from the stream to maximize a noisy set function, which does not need to be 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 provides a □(1/(k+1))-approximation for the noisy models and has a memory independent of the data size. In our numerical experiments, we extensively evaluate the effectiveness of our thresholding streaming algorithm on some real applications datasets.
Short Bio
徐大川，北京工业大学数理学院，教授，博士生导师。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余篇。《J. GTAPH THEORY》等国际著名SCI学术期刊，主持多项国家自然科学基金及省部级课题并著有英文学术论著两部。
Prof. Dr. Xiaoyan Zhang: Max-3-Cut with Limited Unbalance and Application via Complex Semidefinite Programming
Talk Abstract
The use of linear programming for designing approximation algorithms for combinatorial optimization problems has a long tradition. Recently, researchers have investigated the use of nonlinear programming, particularly semidefinite programming, motivated by the seminal paper by Lovász. Semidefinite programs can be solved up to any prescribed accuracy in polynomial time. In this talk, we introduce our recent progress on the problem of Max-3-Cut with limited unbalance, which has application in Scheduling problems via the randomized approximation technique based on complex semidefinite programming relaxation.
Short Bio
张晓岩, 南京师范大学数学科学学院及数学研究所教授，博士生导师，南京师范大学“百名青年领军人才”、“青蓝工程”优秀中青年学术带头人，江苏省六大人才高峰高层次人才，江苏省运筹学监事会监事，中国运筹学图论与组合分会青年理事，荷兰在华学者协会会员，德国波恩大学离散数学研究所及英国伦敦大学皇家洛伦威学院访问教授。主要从事图上组合优化、有向图算法及理论计算机科学的研究工作，研究成果发表在《SIAM J. COMPUTING》、《SIAM J. SCIENTIFIC COMPUTING》、《SIAM J. DISCRETE MATH》及《J. GTAPH THEORY》等国际著名SCI学术期刊，主持多项国家自然科学基金及省部级课题并著有英文学术论著两部。
