报告名称：Packing Feedback Arc Sets in Tournaments Exactly

报告专家：陈旭瑾

专家所在单位：中科院数学与系统科学研究院

报告时间：2022年4月27日14：00-16：00

报告地点:腾讯会议（会议号：187748433）

专家简介：陈旭瑾，女，博士，中国科学院数学与系统科学研究院研究员。1997年毕业于云南大学，获数学理学学士学位（专业：应用数学）。2000年毕业于东南大学，获数学理学硕士学位（方向：图论；导师:宋增民教授）。2004年毕业于香港大学，获数学哲学博士学位（方向：组合优化；导师:臧文安教授）。2004年9月至2006年8月，在中科院应用数学所做博士后（合作导师：胡晓东研究员）。2006年3月至2006年8月，在英国Warwick大学做访问学者。2007年3月至2007年6月在中国香港大学做访问学者。2007年8月至2008年5月，在美国路易日安那州立大学做访问助理教授。2006年9月至2009年2月，在中国科学院数学与系统科学研究院任基地助理研究员。2010年10月至2010年11月在德国Max-Planck Institute for Informatic做访问副教授。2012年3月至2012年5月在加拿大New Brunswick University做访问副教授。2016年至今在中国科学院大学数学科学学院任教授。在《Mathematics of Operations Research》、《SIAM Journal on Computing》、《Algorithmica》、《Journal of Combinatorial Theory, Series B》等运筹学及相关领域国际重要期刊上发表论文四十余篇。在多个期刊杂志担任编委等重要职位。主持参与多个国家重点项目。

报告摘要：LetTbe a tournament with a nonnegative integral weight functionwdefined on its arc setA(T).A subsetFof arcs is called afeedback arc set(FAS) ifTnFcontains no directed cycles. A collectionFofFAS's (with repetition allowed) is called anFAS packingif each arca2A(T) is used at mostw(a) times bythe members ofF. In this talk, we present a characterization of all tournamentsTwith the property that,for every nonnegative integral weight functionwdefined onA(T), the minimum total weight of a directedcycle is equal to the maximum size of an FAS packing. (Joint work with Guoli Ding, Wenan Zang, andQiulan Zhao.)