However, less is known for more complicated constraints. For the problem of maximizing a function with submodularity ratio \(\gamma \)  under an arbitrary matroid constraint, the best known guarantee is a randomized \(1/(1+\gamma ^{-1})^2\) -approximation algorithm via the residual random greedy algorithm due Chen et al. [1]}. However, as \(\gamma \)  tends to 1 (i.e. as the function becomes closer to a submodular function) the approximation tends to only \(1/4\) , while the standard greedy algorithm is known to provide a \(1/2\)  approximation for submodular objectives under a matroid constraint. A major difficulty in obtaining improved guarantees is that the definition of weak submodularity does not provide sufficient structure for the analysis of non-greedy algorithms or more general constraints. In fact, all algorithms working with weakly submodular functions, whether they are designed for streaming, distributed, or offline settings, construct a solution by sequentially selecting elements [2]}, [3]}, [4]}, [5]}. In contrast, the analyses of both local search algorithms and the rounding procedure used in conjunction with the continuous greedy algorithm require considering the effect of swaps of elements on the value of \(f\) . Therefore, it is natural to ask whether many of the real-world applications displaying weak submodularity may have some further inherent property which allows these techniques to be used.
