Recent years have witnessed a growing trend toward employing deep
reinforcement learning (Deep-RL) to derive heuristics for combinatorial
optimization (CO) problems on graphs. Maximum Coverage Problem (MCP) and its
probabilistic variant on social networks, Influence Maximization (IM), have
been particularly prominent in this line of research. In this paper, we present
a comprehensive benchmark study that thoroughly investigates the effectiveness
and efficiency of five recent Deep-RL methods for MCP and IM. These methods
were published in top data science venues, namely S2V-DQN, Geometric-QN, GCOMB,
RL4IM, and LeNSE. Our findings reveal that, across various scenarios, the Lazy
Greedy algorithm consistently outperforms all Deep-RL methods for MCP. In the
case of IM, theoretically sound algorithms like IMM and OPIM demonstrate
superior performance compared to Deep-RL methods in most scenarios. Notably, we
observe an abnormal phenomenon in IM problem where Deep-RL methods slightly
outperform IMM and OPIM when the influence spread nearly does not increase as
the budget increases. Furthermore, our experimental results highlight common
issues when applying Deep-RL methods to MCP and IM in practical settings.
Finally, we discuss potential avenues for improving Deep-RL methods. Our
benchmark study sheds light on potential challenges in current deep
reinforcement learning research for solving combinatorial optimization
problems.

这篇论文通过全面的基准研究，调查了五种最近的深度强化学习方法在最大覆盖问题和影响最大化问题中的有效性和效率，并发现在最大覆盖问题中，Lazy Greedy 算法一直优于所有深度强化学习方法，而在影响最大化问题中，IMM 和 OPIM 算法在大多数场景下表现出优秀性能，但当影响范围几乎不随预算增加而增加时，深度强化学习方法略优于 IMM 和 OPIM 算法。此外，实验结果还突显了在实际场景中应用深度强化学习方法解决最大覆盖问题和影响最大化问题时的一些常见问题，并讨论了提高深度强化学习方法的潜在途径。该基准研究揭示了当前深度强化学习在解决组合优化问题方面可能面临的挑战。

图上最大覆盖问题的深度强化学习方法对比研究

A Benchmark Study of Deep-RL Methods for Maximum Coverage Problems over  Graphs

Pareto optimization using evolutionary multi-objective algorithms has been
widely applied to solve constrained submodular optimization problems. A crucial
factor determining the runtime of the used evolutionary algorithms to obtain
good approximations is the population size of the algorithms which grows with
the number of trade-offs that the algorithms encounter. In this paper, we
introduce a sliding window speed up technique for recently introduced
algorithms. We prove that our technique eliminates the population size as a
crucial factor negatively impacting the runtime and achieves the same
theoretical performance guarantees as previous approaches within less
computation time. Our experimental investigations for the classical maximum
coverage problem confirms that our sliding window technique clearly leads to
better results for a wide range of instances and constraint settings.

本文介绍了一种滑动窗口加速技术，通过使用这种技术减少算法中的种群规模，达到与之前的方法相同的理论性能保证，同时显著提高解决一系列最大覆盖问题实例和约束设置的结果。