主讲人：陈旭瑾研究员，中科院数学与系统科学研究院
报告时间：2020年9月25日15：00
报告地点：腾讯会议 ID：111 258 551
报告题目：Weighted Graph Densities and Fractional Edge-Colorings
报告摘要：Given a multigraph G=(V,E) with edge weight $w\in\mathbb Q_(>0)^E$, the weighted density problem (WDP) is to find a subset U of V with odd size at least 3 such that the density 2w(U)/(|U|-1) is maximized, where w(U) is the total weight of all edges with both ends in U. Even for unit weights, determining whether the WDP can be solved in polynomial time was posed by Jensen and Toft (2015) and by Stiebitz et al. (2012) as an open problem. The WDP is closely related to the weighted fractional edge-coloring problem (WFECP), which is to fractionally decompose G into a minimum amount of matchings. In this talk, we discuss how to solve the WDP and WFECP exactly in strongly polynomial time. (Joint work with Wenan Zang and Qiulan Zhao.)
个人简介：陈旭瑾，2004年获香港大学博士学位，现为中国科学院数学与系统科学研究院研究员。“中国运筹学会青年科技奖”和“国家优秀青年基金”获得者。从事运筹学及相关领域的研究工作，主要研究方向是组合优化的理论和应用，包括算法博弈论、网络优化、多面体组合等。
