2022级博士研究生孙睿同学的论文《An efficient local search algorithm for minimum positive influence dominating set problem》在运筹学领域国际期刊Computer & Operation Research上正式发表。孙睿同学于2022年进入智能信息处理实验室攻读博士学位。

期刊简介：Computer & Operation Research（COR）是运筹学与计算机科学领域的国际权威期刊。该期刊关注计算机和运筹学领域问题的研究，致力于将运筹学与计算机科学的创新性成果应用于生态、交通、安全、可靠性、城市规划、经济、库存控制、投资策略和物流等现实领域。

期刊名称：Computer & Operation Research

期刊类别：中科院2区

第一作者：孙睿

作者顺序：孙睿，巫捷妤，金成厚，王艺源，周文博，殷明浩

通讯作者：殷明浩，王艺源

论文题目：An Efficient Local Search Algorithm for Minimum Positive

Influence Dominating Set Problem

论文概述：最小正影响支配集(MPIDS)问题是最小支配集(MDS)问题的重要扩展问题，在社交网络等领域具有重要应用。相比于MDS问题，目前只有少量研究针对 MPIDS问题提出求解算法。为了更高效地求解该问题，作者提出了一个局部搜索算法FastPIDS，该算法主要包含三个策略。首先，该算法采用了四个约简策略固定一些一定在最优解与一定不在最优解中的顶点，从而减小搜索空间。其次，在充分考虑MPIDS的问题特点后，提出基于两种打分函数的顶点交换策略。最后，作者提出了一个基于二层判断的搜索框架，该框架可以探索更多邻域空间。实验结果表明，该算法在传统测试用例与现实测试用例的性能都明显优于其他MPIDS求解方法。