MAXIMIZING NON-MONOTONE SUBMODULAR FUNCTIONS
MAXIMIZING NON-MONOTONE SUBMODULAR FUNCTIONS
复制标题
DOI：
10.1137/090779346
复制
发表时间：
2011-01-01
影响因子：
1.6
通讯作者：
Vondrak, Jan
中科院分区：
文献类型：
--
作者：
Feige, Uriel;Mirrokni, Vahab S.;Vondrak, Jan
次模极大化推广了许多重要问题，包括有向图、无向图和超图中的最大切割问题、某些约束满足问题和最大设施定位问题。与最小化子模函数的问题不同，最大化子模函数的问题是np困难的。在本文中，我们设计了第一个用于最大化非负（非单调）子模函数的常因子逼近算法。特别地，我们给出了一个确定性的局部搜索1/3逼近算法和一个随机化的2/5逼近算法来最大化非负子模函数。我们还证明了均匀随机集给出1/4近似。对于对称次模函数，我们证明了随机集给出了1/2近似，这也可以通过确定性局部搜索来实现。这些算法在值oracle模型中工作，其中子模函数可以通过一个黑盒访问，对于给定的集合S返回f(S)。我们表明，在这个模型中，对称子模函数的（1/2 + epsilon）近似将需要对任何固定的epsilon >进行指数级查询。在显式给出f的模型中（作为非负子模函数的和，每个函数只依赖于一个常数的元素），我们证明了对称情况下的np -硬度为（5/6 + epsilon）近似，一般情况下的np -硬度为（3/4 + epsilon）近似。
Submodular maximization generalizes many important problems including Max Cut in directed and undirected graphs and hypergraphs, certain constraint satisfaction problems, and maximum facility location problems. Unlike the problem of minimizing submodular functions, the problem of maximizing submodular functions is NP-hard. In this paper, we design the first constant-factor approximation algorithms for maximizing nonnegative (non-monotone) submodular functions. In particular, we give a deterministic local-search 1/3-approximation and a randomized 2/5-approximation algorithm for maximizing nonnegative submodular functions. We also show that a uniformly random set gives a 1/4-approximation. For symmetric submodular functions, we show that a random set gives a 1/2-approximation, which can also be achieved by deterministic local search. These algorithms work in the value oracle model, where the submodular function is accessible through a black box returning f(S) for a given set S. We show that in this model, a (1/2 + epsilon)-approximation for symmetric submodular functions would require an exponential number of queries for any fixed epsilon > 0. In the model where f is given explicitly (as a sum of nonnegative submodular functions, each depending only on a constant number of elements), we prove NP-hardness of (5/6 + epsilon)-approximation in the symmetric case and NP-hardness of (3/4 + epsilon)-approximation in the general case.