Constrained Monotone <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math> </inline-formula>-Submodular Function Maximization Using Multiobjective Evolutionary Algorithms With Theoretical Guarantee
提出一种多目标进化算法，同时最大化单调k-子模函数和最小化规模，在理论上达到与贪心算法相同的渐近紧近似保证，并在影响力最大化等应用中表现更优。
The problem of maximizing monotone <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</i> -submodular functions under a size constraint arises in many applications, and it is NP-hard. In this paper, we propose a new approach which employs a multiobjective evolutionary algorithm to maximize the given objective and minimize the size simultaneously. For general cases, we prove that the proposed method can obtain the asymptotically tight approximation guarantee, which was also achieved by the greedy algorithm. Moreover, we further give instances where the proposed approach performs better than the greedy algorithm on applications of influence maximization, information coverage maximization, and sensor placement. Experimental results on real-world data sets exhibit the superior performance of the proposed approach.