MONOTONE SUBMODULAR MAXIMIZATION OVER A MATROID VIA NON-OBLIVIOUS LOCAL SEARCH
MONOTONE SUBMODULAR MAXIMIZATION OVER A MATROID VIA NON-OBLIVIOUS LOCAL SEARCH
复制标题
DOI：
10.1137/130920277
复制
发表时间：
2014-01-01
影响因子：
1.6
通讯作者：
Ward, Justin
中科院分区：
文献类型：
--
作者：
Filmus, Yuval;Ward, Justin
我们提出了一种最佳的，组合的1-1/e近似算法，用于单调在矩阵约束上的单调次数优化。与连续的贪婪算法相比[G. Calinescu等人，IPCO，Springer，柏林，2007年，第182-196页]我们的算法非常简单，不需要舍入。它由贪婪的算法组成，然后是本地搜索。这两个阶段不是在实际的目标函数上运行，而是基于相关的辅助电位函数，该功能也是单调和下管。在我们先前关于最大覆盖范围的工作中[Y. Filmus和J. Ward，Focs，IEEE，Piscataway，新泽西州，2012年，第659-668页，潜在功能使多次涵盖的元素的重量更大。我们将这种方法从覆盖函数到任意单调下调函数概括。当目标函数是覆盖函数时，潜在函数的两个定义重合。我们的方法概括了单调下函数具有限制曲率的情况。对于任何曲率C，我们适应算法以产生A（1 -e（-c））/C近似。这与Vondrak [STOC，ACM，纽约，2008年，第67-74页]的结果相匹配，后者表明，当目标函数具有曲率时，连续的贪婪算法会产生A（1-E（-C））/C近似C相对于最佳，并证明在值Oracle模型中不可能实现任何更好的近似值。
We present an optimal, combinatorial 1-1/e approximation algorithm for monotone submodular optimization over a matroid constraint. Compared to the continuous greedy algorithm [G. Calinescu et al., IPCO, Springer, Berlin, 2007, pp. 182-196] our algorithm is extremely simple and requires no rounding. It consists of the greedy algorithm followed by a local search. Both phases are run not on the actual objective function, but on a related auxiliary potential function, which is also monotone and submodular. In our previous work on maximum coverage [Y. Filmus and J. Ward, FOCS, IEEE, Piscataway, NJ, 2012, pp. 659-668], the potential function gives more weight to elements covered multiple times. We generalize this approach from coverage functions to arbitrary monotone submodular functions. When the objective function is a coverage function, both definitions of the potential function coincide. Our approach generalizes to the case where the monotone submodular function has restricted curvature. For any curvature c, we adapt our algorithm to produce a (1 - e(-c))/c approximation. This matches results of Vondrak [STOC, ACM, New York, 2008, pp. 67-74], who has shown that the continuous greedy algorithm produces a (1 - e(-c))/c approximation when the objective function has curvature c with respect to the optimum, and proved that achieving any better approximation ratio is impossible in the value oracle model.