Approximation algorithms for finding a densest k-subhypergraph
主 讲 人 ：陈旭瑾 教授
活动时间：12月13日16时00分
地 点 ：理科群 1号楼 D-203室 腾讯会议号：571 277 314 密码：231213
讲座内容：
Given a hypergraph H with order n and rank at most r, a subhypergraph of H with order k is called a k-subhypergraph. We present an O(n^{(r-1)/2})-approximation algorithm for finding a densest (connected) k-subhypergraph of H. Our algorithm particularly gives an O(n^{1/2})-approximation for the densest connected k-subgraph problem, which improves upon the previous best-known approximation ratio O(n^{2/3}). (Joint work with Xiaodong Hu, Changjun Wang, and Qingjie Ye).
主讲人介绍：
陈旭瑾，2004年获香港大学博士学位，现为中国科学院数学与系统科学研究院研究员。主要研究兴趣是组合优化的理论和算法，包括算法博弈论、网络优化、多面体组合等。曾获中国青年科技奖、中国运筹学会青年科技奖、国家优秀青年基金。入选国家“万人计划”科技创新领军人才。
