登录

Packing Feedback Arc Sets in Tournaments Exactly
[  作者:    人气:  创建时间:2022/04/27  ]

报告名称: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.)