Submodularity, a discrete analog of convexity, is a key property in discrete optimization that features in the construction of valid inequalities and analysis of the greedy algorithm. In this paper, we broaden the approximate submodularity literature, which so far has largely focused on variants of greedy algorithms and iterative approaches. We define metrics that quantify approximate submodularity and use these metrics to derive properties about approximate submodularity preservation and extensions of set functions. We show that previous analyses of mixed-integer sets, such as the submodular knapsack polytope, can be extended to the approximate submodularity setting. In addition, we demonstrate that greedy algorithm bounds based on our notions of approximate submodularity are competitive with those in the literature, which we illustrate using a generalization of the uncapacitated facility location problem.
Article
View Approximate Submodularity and Its Implications in Discrete Optimization