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 ϵ > 0, there is a natural local search algorithm that has approximation guarantee of 1/(k + ϵ) 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 (1978). 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 + ϵ) and 1/(k + 1 + 1/(k-1) + ϵ), 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.
