Galaxy·银河8366cc 加入收藏 English
当前位置: 首页 >> 通知公告 >> 正文 通知公告
学术报告第53讲:Supermodular Maximization with Cardinality Constraints
来源:  点击次数: 次 发布时间:2023-11-10   编辑:Galaxy·银河8366cc(中国)官方网站

学术报告:Supermodular Maximization with Cardinality Constraints




报告摘要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})).



          地址:北京市昌平区沙河高教园中央财经大学沙河校区1号学院楼   邮政编码:102206   电 话:(010)61776184