学术报告：Supermodular Maximization with Cardinality Constraints

报告时间：2023年11月15日（星期三）下午15:00-16:00

报告地点：沙河校区，二教112

报告人：王长军，中国科学院数学与系统科学研究院，副研究员

报告摘要：Let V be a finite set of cardinality |V|=n and k be a positive integer at most n. We are concerned with maximization over nonnegative monotone supermodular set function f subject to cardinality constraint: finding a subset S in V with |S|<= k such that f(S) is as large as possible. The function f is r-decomposable, where r is a positive integer at most n, if there exist m subsets V_1, …, V_m of V each with cardinality at most r and nonnegative supermodular functions f_i, i=1, …, m such that f(S) =\sum_{i=1}^m f_i(S \cap V_i) holds for each S in V. Given r as an input, we find an O(n^{(r-1)/2})-approximation in polynomial time without knowing the decomposition. When the decomposition is given, let G be the graph with vertex set V and edge set E= {uv:u,v in V_i,u v are distinct}. We additionally require that the solution set S in V induces a connected subgraph in G. We propose a polynomial time O(n^{(r-1)/2})-approximation algorithm for this problem when r is constant, which implies an O(n^{1/2}) approximation for the densest connected k-subgraph problem (improving upon the previous best-known approximation ratio O(n^{2/3})).

报告人简介：王长军，中科院数学与系统科学研究院优秀青年副研究员，2015年博士毕业于中科院数学与系统科学研究院运筹学专业。主要从事算法博弈与机制设计、组合优化等方向的研究。目前已在包括OR、MOR、POM、EC、WINE等的相关领域国际期刊及会议发表论文二十多篇。曾主持国家自然科学基金面上、青年项目和中国科协青年人才托举工程项目等。