2022年6月17日19: 30-21：00，排序与调度网络公益讲堂（第十期）在腾讯会议和B站顺利举办，主讲人是杭州电子科技大学张安教授。本期公益讲堂由中国运筹学会排序分会副理事长、华东理工大学刘朝晖教授主持，中国运筹学会排序分会前任理事长、上海第二工业大学唐国春教授等人聆听了本场精彩的学术报告。

        首先，刘老师介绍了张老师的基本信息，并对张老师表示热烈的欢迎与真挚的感谢，随后张老师开始了以“冲突图约束的排序问题”为主题的精彩报告。

       冲突图约束的排序问题是一种特殊的图约束排序，在研究方法上具有鲜明的特点。在该问题中，工件的冲突关系用一个简单图来刻画，称为冲突图（其补图称为许可图）。张老师首先介绍了研究该问题所用的匹配工具，综述了问题的研究现状。随后，对一个特殊情形即{2;3}-问题，介绍了4个基于最大匹配、度约束匹配或最大权匹配的近似算法，证明其近似比是5/4或者7/6，且是紧的。然后，重点介绍了双匹配算法的设计过程以及近似比的分析技巧，证明近似比上界是8/7，下界是13/12。最后，通过3维匹配问题多项式归约证明了{2;3}-问题的强NP-困难性，并提出了冲突图排序中若干待解决的问题。

       在报告结束之后，张老师悉心回答了刘朝晖、余炜教授等老师和同学提出的问题。最后，马冉教授代表报告听众对报告人张老师及中国运筹学会排序分会的前辈们对公益讲堂系列的大力支持表示深深的敬意和美好的祝愿！

                                                                                                                （曲阜师范大学王靖雯、张龙供稿）

向所有推动排序与调度发展的前辈和老师致敬！