论文标题
稳健序列网络的supproular suppular最大化
Robust Sequence Networked Submodular Maximization
论文作者
论文摘要
在本文中，我们研究\下划线{r} obust \下划线{o} \ \下划线{se} quence \ quence \ usewence \ usewence \ usewistline {net}工作\下划线{s} ubmodular maximization（rosenets）问题。我们将强大的优化与序列网络的下区性最大化交织在一起。元素通过有向的无环图连接，并且目标函数在元素上不是在图中的边缘上进行的。在这样的网络集合场景下，从序列中删除元素的影响既取决于其在序列和网络中的位置。这使现有的强大算法不适用。在本文中，我们迈出了研究Rosenets问题的第一步。我们设计了一种强大的贪婪算法，该算法可与选择选定元素的任意子集进行稳定。该算法的近似值均取决于去除元素的数量和网络拓扑的数量。我们进一步进行有关建议和链接预测的实际应用实验。实验结果证明了所提出的算法的有效性。
In this paper, we study the \underline{R}obust \underline{o}ptimization for \underline{se}quence \underline{Net}worked \underline{s}ubmodular maximization (RoseNets) problem. We interweave the robust optimization with the sequence networked submodular maximization. The elements are connected by a directed acyclic graph and the objective function is not submodular on the elements but on the edges in the graph. Under such networked submodular scenario, the impact of removing an element from a sequence depends both on its position in the sequence and in the network. This makes the existing robust algorithms inapplicable. In this paper, we take the first step to study the RoseNets problem. We design a robust greedy algorithm, which is robust against the removal of an arbitrary subset of the selected elements. The approximation ratio of the algorithm depends both on the number of the removed elements and the network topology. We further conduct experiments on real applications of recommendation and link prediction. The experimental results demonstrate the effectiveness of the proposed algorithm.
