Approximating submodular functions everywhere

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.

Authors

• Michel X. Goemans
• Nicholas J. A. Harvey
• Satoru Iwata 0001
• Vahab Mirrokni

Keywords

No keywords are indexed for this paper.