报告时间：2018年5月23日下午16:20-17:00

报告地点：数学与统计学院106报告厅

报告人：中国科学院 陈旭瑾研究员

报告题目：Improved approximation for connected densest k-subgraphs

摘要：Given an edge-weighted connected graph G on n vertices and an integer k≤ n, a subgraph of G is called a k-subgraph if it contains exactly k vertices. The (weighted) density of a subgraph is the average (weighted) degree of all vertices of this subgraph. We study the problem of finding a connected k-subgraph of G with the maximum weighted density. We propose a combinatorial polynomial-time algorithm for the problem which achieves an approximation ratio of O(n/k). The weighted density of the k-subgraph in G found by the algorithm is at least a factor Ω(k/n) of the maximum weighted density among all subgraphs in G with at least k vertices (which are not necessarily connected). The result improves upon the previously known best approximation ratio O(n^2/k^2) for the problem, and matches the current best approximation ratio O(n/k), in terms of n and k, for finding a k-subgraph with the maximum density. The O(n/k)-approximation algorithm combined with the previous O(k)-approximation algorithm of Chen et al. [Information and Computation 2017] finds a connected k-subgraph in G whose weighted density is at least a factor Ω(1/√n) of the maximum weighted density among all k-subgraphs. This is the best possible one can derive since the ratio of the maximum weighted density of a k-subgraph in G to that of a connected k-subgraph in G can be as large as Ω(√n). (Joint work with Changjun Wang.)

报告人简介：陈旭瑾，女，博士，中国科学院数学与系统科学研究院副研究员。1997年毕业于云南大学，获数学理学学士学位 （专业：应用数学）。2000年毕业于东南大学，获数学理学硕士学位 （方向：图论； 导师: 宋增民教授）。2004年毕业于香港大学，获数学哲学博士学位 （方向：组合优化； 导师: 臧文安教授）。2004年9月至2006年8月，在中科院应用数学所做博士后（合作导师：胡晓东研究员）。2006年3月至2006年8月，在英国Warwick大学做访问学者。2006年9月至2009年2月，在中国科学院数学与系统科学研究院任基地助理研究员。2007年8月至2008年5月，在美国路易日安那州立大学做访问助理教授。