论文标题
通过屏障功能的次生次数最大化
Submodular Maximization Through Barrier Functions
论文作者
论文摘要
在本文中，我们引入了一种新型技术，用于受约束的次体最大化，这是受持续优化的障碍功能的启发。该连接不仅可以改善受约束的下管最大化的运行时间，而且还提供了艺术保证的状态。更确切地说，为了最大化单调的supdodular函数，但要结合$ k $ -matchoid和$ \ ell $ -knapsack约束（对于$ \ ell \ ell \ leq k $），我们提出了一个可以近似最小化的潜在功能。一旦我们将潜在函数最小化至$ε$错误，可以保证我们发现了一个可行的设置，该集合具有$ 2（K+1+ε）$ - 近似因子，确实可以通过枚举技术将其进一步提高到$（K+1+ε）$。我们广泛评估了在几个现实世界应用程序中提出的算法的性能，包括电影推荐系统，YouTube视频的摘要任务，Twitter feed和Yelp Business位置以及设置封面问题。
In this paper, we introduce a novel technique for constrained submodular maximization, inspired by barrier functions in continuous optimization. This connection not only improves the running time for constrained submodular maximization but also provides the state of the art guarantee. More precisely, for maximizing a monotone submodular function subject to the combination of a $k$-matchoid and $\ell$-knapsack constraint (for $\ell\leq k$), we propose a potential function that can be approximately minimized. Once we minimize the potential function up to an $ε$ error it is guaranteed that we have found a feasible set with a $2(k+1+ε)$-approximation factor which can indeed be further improved to $(k+1+ε)$ by an enumeration technique. We extensively evaluate the performance of our proposed algorithm over several real-world applications, including a movie recommendation system, summarization tasks for YouTube videos, Twitter feeds and Yelp business locations, and a set cover problem.
