In this work, we present a new algorithm for maximizing a non-monotone submodular function subject to a general constraint. Our algorithm finds an approximate fractional solution for maximizing the multilinear extension of the function over a down-closed polytope. The approximation guarantee is 0.372 and it is the first improvement over the 1 e approximation achieved by the unified Continuous Greedy algorithm [, FOCS 2011].
Submodular maximization problems are well-studied and it is hard to do justice to all previous literature on this subject. Starting with the seminal work @cite_14 , the classical approaches to these problems are largely combinatorial and based on greedy and local search algorithms. Over the years, with increasing sophistication, this direction has led to many tight results such as the algorithm of @cite_4 for a knapsack constraint, and the current best results for constraints such as multiple matroid constraints @cite_15 . In the last few years, another approach emerged @cite_0 that follows the popular paradigm in approximation algorithms of optimizing a continuous relaxation and rounding the resulting fractional solution. A key difficulty that separates the submodular setting from the classical setting is that even finding a may be quite challenging, and in particular it is @math -hard to solve the continuous relaxation for maximizing submodular functions that is based on the multilinear extension. Thus, a line of work has been developed to optimize this relaxation @cite_0 @cite_17 @cite_7 @cite_12 culminating in the work @cite_12 , which we extend here.
@cite_14 @cite_4 @cite_7 @cite_0 @cite_15 @cite_12 @cite_17
1997783781 2033885045 2621717961 2802297243 2045492898 2026338082
A real-valued function z whose domain is all of the subsets of N = 1,..., n is said to be submodular if zS + zT ≥ zS ∪ T + zS ∩ T, ∀S, T ⊆ N, and nondecreasing if zS ≤ zT, ∀S ⊂ T ⊆ N. We consider the problem maxS⊂N zS: |S| ≤ K, z submodular and nondecreasing, zO = 0 . Many combinatorial optimization problems can be posed in this framework. For example, a well-known location problem and the maximization of certain boolean polynomials are in this class. We present a family of algorithms that involve the partial enumeration of all sets of cardinality q and then a greedy selection of the remaining elements, q = 0,..., K-1. For fixed K, the qth member of this family requires Onq+1 computations and is guaranteed to achieve at least @math Our main result is that this is the best performance guarantee that can be obtained by any algorithm whose number of computations does not exceed Onq+1. In this paper, we obtain an (1-e^-^1)-approximation algorithm for maximizing a nondecreasing submodular set function subject to a knapsack constraint. This algorithm requires O(n^5) function value computations. Submodular function maximization is a central problem in combinatorial optimization, generalizing many important NP-hard problems including max cut in digraphs, graphs, and hypergraphs; certain constraint satisfaction problems; maximum entropy sampling; and maximum facility location problems. Our main result is that for any k ≥ 2 and any e > 0, there is a natural local search algorithm that has approximation guarantee of 1 (k + e) for the problem of maximizing a monotone submodular function subject to k matroid constraints. This improves upon the 1 (k + 1)-approximation of Fisher, Nemhauser, and Wolsey obtained in 1978 [Fisher, M., G. Nemhauser, L. Wolsey. 1978. An analysis of approximations for maximizing submodular set functions---II. Math. Programming Stud.8 73--87]. Also, our analysis can be applied to the problem of maximizing a linear objective function and even a general nonmonotone submodular function subject to k matroid constraints. We show that, in these cases, the approximation guarantees of our algorithms are 1 (k-1 + e) and 1 (k + 1 + 1 (k-1) + e), respectively. Our analyses are based on two new exchange properties for matroids. One is a generalization of the classical Rota exchange property for matroid bases, and another is an exchange property for two matroids based on the structure of matroid intersection. The study of combinatorial problems with a sub modular objective function has attracted much attention in recent years, and is partly motivated by the importance of such problems to economics, algorithmic game theory and combinatorial optimization. Classical works on these problems are mostly combinatorial in nature. Recently, however, many results based on continuous algorithmic tools have emerged. The main bottleneck of such continuous techniques is how to approximately solve a non-convex relaxation for the sub modular problem at hand. Thus, the efficient computation of better fractional solutions immediately implies improved approximations for numerous applications. A simple and elegant method, called continuous greedy'', successfully tackles this issue for monotone sub modular objective functions, however, only much more complex tools are known to work for general non-monotone sub modular objectives. In this work we present a new unified continuous greedy algorithm which finds approximate fractional solutions for both the non-monotone and monotone cases, and improves on the approximation ratio for many applications. For general non-monotone sub modular objective functions, our algorithm achieves an improved approximation ratio of about @math . For monotone sub modular objective functions, our algorithm achieves an approximation ratio that depends on the density of the poly tope defined by the problem at hand, which is always at least as good as the previously known best approximation ratio of @math . Some notable immediate implications are an improved @math -approximation for maximizing a non-monotone sub modular function subject to a matroid or @math -knapsack constraints, and information-theoretic tight approximations for Sub modular Max-SAT and Sub modular Welfare with @math players, for any number of players @math . A framework for sub modular optimization problems, called the , was introduced recently by The improved approximation ratio of the unified continuous greedy algorithm implies improved approximation ratios for many problems through this framework. Moreover, via a parameter called , our algorithm merges the relaxation solving and re-normalization steps of the framework, and achieves, for some applications, further improvements. We also describe new monotone balanced contention resolution schemes for various matching, scheduling and packing problems, thus, improving the approximations achieved for these problems via the framework. Submodular function maximization is a central problem in combinatorial optimization, generalizing many important problems including Max Cut in directed undirected graphs and in hypergraphs, certain constraint satisfaction problems, maximum entropy sampling, and maximum facility location problems. Unlike submodular minimization, submodular maximization is NP-hard. In this paper, we give the first constant-factor approximation algorithm for maximizing any non-negative submodular function subject to multiple matroid or knapsack constraints. We emphasize that our results are for non-monotone submodular functions. In particular, for any constant k, we present a (1 k+2+1 k+e)-approximation for the submodular maximization problem under k matroid constraints, and a (1 5-e)-approximation algorithm for this problem subject to k knapsack constraints (e>0 is any constant). We improve the approximation guarantee of our algorithm to 1 k+1+ 1 k-1 +e for k≥2 partition matroid constraints. This idea also gives a ( 1 k+e)-approximation for maximizing a monotone submodular function subject to k≥2 partition matroids, which improves over the previously best known guarantee of 1 k+1.