text: We design new approximation algorithms for the problems of optimizing submodular and supermodular functions subject to a single matroid constraint. Specifically, we consider the case in which we wish to maximize a nondecreasing submodular function or minimize a nonincreasing supermodular function in the setting of bounded total curvature @math . In the case of submodular maximization with curvature @math , we obtain a @math -approximation --- the first improvement over the greedy @math -approximation of Conforti and Cornuejols from 1984, which holds for a cardinality constraint, as well as recent approaches that hold for an arbitrary matroid constraint. Our approach is based on modifications of the continuous greedy algorithm and non-oblivious local search, and allows us to approximately maximize the sum of a nonnegative, nondecreasing submodular function and a (possibly negative) linear function. We show how to reduce both submodular maximization and supermodular minimization to this general problem when the objective function has bounded total curvature. We prove that the approximation results we obtain are the best possible in the value oracle model, even in the case of a cardinality constraint. We define an extension of the notion of curvature to general monotone set functions and show @math -approximation for maximization and @math -approximation for minimization cases. Finally, we give two concrete applications of our results in the settings of maximum entropy sampling, and the column-subset selection problem.
  @cite_18: Abstract For the problem maxlcub; Z ( S ): S is an independent set in the matroid X rcub;, it is well-known that the greedy algorithm finds an optimal solution when Z is an additive set function (Rado-Edmonds theorem). Fisher, Nemhauser and Wolsey have shown that, when Z is a nondecreasing submodular set function satisfying Z (∅)=0, the greedy algorithm finds a solution with value at least half the optimum value. In this paper we show that it finds a solution with value at least 1 (1 + α) times the optimum value, where α is a parameter which represents the ‘total curvature’ of Z . This parameter satisfies 0≤α≤1 and α=0 if and only if the set function Z is additive. Thus the theorems of Rado-Edmonds and Fisher-Nemhauser-Wolsey are both contained in the bound 1 (1 + α). We show that this bound is best possible in terms of α. Another bound which generalizes the Rado-Edmonds theorem is given in terms of a ‘greedy curvature’ of the set function. Unlike the first bound, this bound can prove the optimality of the greedy algorithm even in instances where Z is not additive. A third bound, in terms of the rank and the girth of X , unifies and generalizes the bounds (e−1) e known for uniform matroids and 1 2 for general matroids. We also analyze the performance of the greedy algorithm when X is an independence system instead of a matroid. Then we derive two bounds, both tight: The first one is [1−(1−α K ) k ] α where K and k are the sizes of the largest and smallest maximal independent sets in X respectively; the second one is 1 ( p +α) where p is the minimum number of matroids that must be intersected to obtain X .
  @cite_15: Let (X;I) be a matroid and let f : 2 X ! R+ be a monotone submodular function. The curvature of f is the minimum c 2 [0; 1] such that for any S X and j 2 X n S, f (S [ fjg) f (S) (1 c)f (fjg). We consider the optimization problem maxff (S) : S 2 Ig. It is known that the greedy algorithm yields a 1=2-approximation for this problem [10], and 1 1+c -approximation when f has curvature c [3]. For the uniform matroid, it was known that the greedy algorithm yields an improved 1 (1 e c )-approximation [3]. In this paper, we analyze the continuous greedy algorithm [19] and prove that it gives a 1 c (1 e c )-approximation for any matroid. Moreover, we show that this holds for a relaxed notion of curvature, curvature with respect to the optimum, and we prove that any better approximation under these conditions would require an exponential number of value queries.
summary: Conforti and Cornu ' e jols @cite_18 defined the @math of non-decreasing submodular function @math as They showed that greedy algorithm has an approximation ratio of @math for the problem of maximizing a nondecreasing submodular function with curvature at most @math subject to a single matroid constraint. In the special case of a uniform matroid, they were able to show that the greedy is a @math -approximation algorithm. Later, Vondr ' a k @cite_15 considered the continuous greedy algorithm in the setting of bounded curvature. He introduced the notion of , which is a weaker notion than total curvature, and showed that the continuous greedy algorithm is a @math -approximation for maximizing a nondecreasing submodular function @math subject to an arbitrary matroid constraint whenever @math has curvature at most @math with respect to the optimum. He also showed that it is impossible to obtain a @math -approximation in this setting when evaluating @math on only a polynomial number of sets. Unfortunately, unlike total curvature, it is in general not possible to compute the curvature of a function with respect to the optimum, as it requires knowledge of an optimal solution.