学校主页 加入收藏 English
当前位置: 首页 >> 通知公告 >> 正文 通知公告
学术报告第53讲:Supermodular Maximization with Cardinality Constraints
来源:  点击次数: 次 发布时间:2023-11-10   编辑:太阳成集团tyc234cc古天乐

学术报告: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等的相关领域国际期刊及会议发表论文二十多篇。曾主持国家自然科学基金面上、青年项目和中国科协青年人才托举工程项目等。

首页

          版权所有:太阳成集团tyc234cc古天乐  
          地址:北京市昌平区沙河高教园中央财经大学沙河校区1号学院楼   邮政编码:102206   电 话:(010)61776184    
          邮箱:samofcufe@cufe.edu.cn    
         

学院公众号