论文标题
强大的序列supproular最大化
Robust Sequence Submodular Maximization
论文作者
论文摘要
间相性是集合功能的重要属性，并且在文献中已经进行了广泛的研究。 IT模型设置功能，显示出较少的回报属性，其中将元素添加到集合随着集合的扩展而减小的边际值会减小。该概念已被推广到考虑序列函数，其中添加元素的顺序起着至关重要的作用并确定函数值。广义概念称为序列（或字符串）子二次性。在本文中，我们研究了稳健序列的新问题，具有基数限制。鲁棒性违反了所选序列中元素的子集（例如，由于出现故障或对抗性攻击）。与稳定的集合功能最大化相比，涉及序列功能时会出现新的挑战。具体而言，序列函数有多种定义，这些定义表现出微妙而关键的差异。另一个挑战来自两个单调性的方向：前向单调性和向后的单调性，这对于证明性能保证都很重要。 To address these unique challenges, we design two robust greedy algorithms: while one algorithm achieves a constant approximation ratio but is robust only against the removal of a subset of contiguous elements, the other is robust against the removal of an arbitrary subset of the selected elements but requires a stronger assumption and achieves an approximation ratio that depends on the number of the removed elements.最后，我们将分析概括为基于序列的近似版本和向后单调性的近似版本，以考虑较弱的假设下的序列函数
Submodularity is an important property of set functions and has been extensively studied in the literature. It models set functions that exhibit a diminishing returns property, where the marginal value of adding an element to a set decreases as the set expands. This notion has been generalized to considering sequence functions, where the order of adding elements plays a crucial role and determines the function value; the generalized notion is called sequence (or string) submodularity. In this paper, we study a new problem of robust sequence submodular maximization with cardinality constraints. The robustness is against the removal of a subset of elements in the selected sequence (e.g., due to malfunctions or adversarial attacks). Compared to robust submodular maximization for set function, new challenges arise when sequence functions are concerned. Specifically, there are multiple definitions of submodularity for sequence functions, which exhibit subtle yet critical differences. Another challenge comes from two directions of monotonicity: forward monotonicity and backward monotonicity, both of which are important to proving performance guarantees. To address these unique challenges, we design two robust greedy algorithms: while one algorithm achieves a constant approximation ratio but is robust only against the removal of a subset of contiguous elements, the other is robust against the removal of an arbitrary subset of the selected elements but requires a stronger assumption and achieves an approximation ratio that depends on the number of the removed elements. Finally, we generalize the analyses to considering sequence functions under weaker assumptions based on approximate versions of sequence submodularity and backward monotonicity
