Approximating Submodular Functions Everywhere
Michel X. Goemans, Nicholas J. A. Harvey, Satoru Iwata, Vahab Mirrokni · Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms · 2009
Submodular functions are a key concept in combinatorial optimization. Algorithms that involve submodular functions usually assume that they are given by a (value) oracle. Many interesting problems involving submodular functions can be solved using only polynomially many queries to the oracle, e.g., exact minimization or approximate maximization. In this paper, we consider the problem of approximating a non-negative, monotone, submodular function f on a ground set of size n everywhere, after only poly(n) oracle queries. Our main result is a deterministic algorithm that makes poly(n) oracle queries and derives a function such that, for every set S, (S) approximates f(S) within a factor α(n), where for rank functions of matroids and for general monotone submodular functions. Our result is based on approximately finding a maximum volume inscribed ellipsoid in a symmetrized polymatroid, and the analysis involves various properties of submodular functions and polymatroids. Our algorithm is tight up to logarithmic factors. Indeed, we show that no algorithm can achieve a factor better than , even for rank functions of a matroid.