报告题目：Packing Feedback Arc Sets in Tournaments Exactly

报 告 人：陈旭瑾，中国科学院数学与系统科学研究院研究员

报告摘要：Let T be a tournament with a nonnegative integral weight function w defined on its arc set A(T). A subset F of arcs is called a feedback arc set (FAS) if T\F contains no directed cycles. A collection F of FAS's (with repetition allowed) is called an FAS packing if each arc a∈A(T) is used at most w(a) times by the members of F. In this talk, we present a characterization of all tournaments T with the property that, for every nonnegative integral weight function w defined on A(T), the minimum total weight of a directed cycle is equal to the maximum size of an FAS packing. (Joint work with Guoli Ding, Wenan Zang, and Qiulan Zhao.)

报告人简介：陈旭瑾，2004年获香港大学博士学位，现为中国科学院数学与系统科学研究院研究员，主要研究兴趣是组合优化的理论和算法，包括算法博弈论、网络优化、多面体组合等。曾获“中国青年科技奖”“中国运筹学会青年科技奖”和“国家优秀青年基金”。个人主页：http://people.ucas.ac.cn/~xchen?language=en.

报告时间：2021年11月21日15:00--16:00

报告地点：腾讯会议，ID: 511 887 594

报告邀请人：图论组合优化科研团队

主办单位：伟德国际1946源自英国