论文标题
单调非管子最大化的有效算法，分区矩阵约束
Efficient Algorithms for Monotone Non-Submodular Maximization with Partition Matroid Constraint
论文作者
论文摘要
在这项工作中，我们研究了单调非管状最大化的问题，并通过分区矩阵约束。尽管在文献中已经研究了此问题的概括，但我们的工作着重于将分区矩阵约束的特性提出（1）提出具有理论界限和有效的查询复杂性的算法； （2）对某些现有技术的理论性能保证提供更好的分析。我们进一步研究了这些算法在两个应用中的性能：增强影响的传播和视频摘要。实验显示我们的算法将比较结果返回到最新算法的同时，同时进行了更少的查询。
In this work, we study the problem of monotone non-submodular maximization with partition matroid constraint. Although a generalization of this problem has been studied in literature, our work focuses on leveraging properties of partition matroid constraint to (1) propose algorithms with theoretical bound and efficient query complexity; and (2) provide better analysis on theoretical performance guarantee of some existing techniques. We further investigate those algorithms' performance in two applications: Boosting Influence Spread and Video Summarization. Experiments show our algorithms return comparative results to the state-of-the-art algorithms while taking much fewer queries.
