Maximization of Approximately Submodular Functions

We study the problem of maximizing a function that is approximately submodular under a cardinality constraint. Approximate submodularity implicitly appears in a wide range of applications as in many cases errors in evaluation of a submodular function break submodularity. Say that F is varepsilon-approximately submodular if there exists a submodular function f such that (1-varepsilon)f(S) ≤ F(S)≤ (1+varepsilon)f(S) for all subsets S. We are interested in characterizing the query-complexity of maximizing F subject to a cardinality constraint k as a function of the error level varepsilon>0. We provide both lower and upper bounds: for varepsilon>n-1/2 we show an exponential query-complexity lower bound. In contrast, when varepsilon< 1/k or under a stronger bounded curvature assumption, we give constant approximation algorithms.