一、题目

The Adaptive Complexity for Submodular Optimization

二、报告人

徐大川，北京工业大学数理学院教授

三、邀请人

张鹏，山东大学软件学院副教授

四、时间

2019年10月15日9:00am–10:30am.

五、地点

软件学院办公楼202会议室

六、摘要

Balkanski and Singer (STOC'18) initiate the study of adaptivity (or parallelism) for maximizing a submodular function with a cardinality constraint. This work invokes subsequent improvements or extensions for submodular maximization with adaptive complexity. In this talk, we review these models, algorithms and complexities. We also introduce some open problems for future research.

七、报告人简介

徐大川，北京工业大学数理学院运筹学与控制论责任教授，博士生导师。北京工业大学区块链研究中心副主任。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 Global Optimization、Journal of Combinatorial Optimization、Information Process Letters、Operations Research Letters等发表学术论文100余篇。