报告（一）

题目：StreamingSubmodular Maximization under Noises

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

时间：2019年4月9日（周二）9:45� 10:30

地点：五教5205教室

摘要：Motivated by theneed for analyzing the rapidly producing data streams, such as images, videos,sensor data, etc, in a timely manner, the study on the streaming algorithms toextract representative information from massive data to maximize some objectivefunction is therefore important and urgent. Most of previous works are assumedunder a noise-free environment, while in many realistic applications obtainingthe 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 generalproblem to select a subset of at most $k$ elements from the stream to maximizea noisy set function (not necessarily submodular). To be specific, we cast ourproblem as the streaming submodular maximization problem with multiplicativeand additive noise models. We develop an efficient thresholding streamingalgorithm, which is $/frac{1}{k+1}$-approximation for both of noisy models andhas a memory independent of data size. In our numerical experiments, weextensively evaluate the effectiveness of our thresholding streaming algorithmon some applications in real data set.

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

题目：Onpartially disjoint paths

报告人：福州大学  郭龙坤副教授

时间：2019年4月9日（周二）10:35� 11:20

地点：五教5205教室

报告摘要：The classicaldisjoint shortest path problem has recently recalled interests from researchersin the networks planning and optimization community. However, the requirementof the shortest paths being completely vertex or edge disjoint might be toorestrictive and demands much more resources in a network. Partial disjointshortest paths, in which a bounded number of shared vertices or edges isallowed, balance between degree of disjointness and occupied network resources.We consider the δ-vertex k edge-disjoint shortest path problem (δV-kEDSP), thatis, for a pair of distinct vertices in a network graph, it optimally finds kedge-disjoint shortest paths between them where at most δ vertices are sharedby at least two paths. We present techniques for exactly solving δV-2EDSP, whichsignificantly improves the runtime bound of the state-of-art. The proposedtheoretical approaches are also validated by computer experiments on bothsynthetic and real networks which demonstrate their superior efficiency of upto three orders of magnitude faster than the state-of-art solution.

报告人简介：郭龙坤，博导，福州大学旗山学者，福州大学数学与计算机科学学院副教授，计算机系主任。主要研究领域为组合优化、算法设计与分析、并行分布式计算等。当前的研究兴趣主要集中于运筹学与计算机理论科学方法在计算机网络、数据科学等领域的应用。已发表SCI/EI/ISTP收录的国内外期刊与会议论文三十余篇,包括IEEE transactions on mobile computing(TMC), IEEE transactions on computers(TC),Algorithmica, IEEE transactions on parallel and distributed systems (TPDS) 等国际期刊及ACMSymposium on Parallelism in Algorithms and Architectures (SPAA), IJCAI等国际会议。PDCAT,PAAP与Cloud-asia等会议的委员会成员（PCMember）．主持在研/完成一项国家自然科学面上基金与一项青年基金，以及多项省部自然科学基金。作为主要参与人参加多项国家与省部自然科学基金。