Generalizing Performance Bounds for the Greedy Algorithm: Approximate Submodularity and Localization.

The greedy algorithm is perhaps the simplest heuristic in combinatorial optimization. When maximizing a nonnegative, increasing, submodular function, the greedy algorithm has a worst-case performance bound proportional to its optimal objective value at a given cardinality. We introduce new metrics that quantify a function's proximity to being submodular. Using our proposed criteria, we derive performance bounds for the greedy algorithm applied to non-submodular functions. Insights from our initial derivations allow us to generalize existing bounds, satisfy the criteria, and improve upon the numerical bounds. We examine multiple bounds using a generalization of the facility location problem that does not have a submodular objective function generally. In numerical examples, our new bounds are competitive with, and often an improvement on, those of Das and Kempe (2011), Horel and Singer (2016), and Zhou and Spanos (2016). We observe this collection of bounds provides complementary information about the optimized function.