Eastern Great Lakes Theory Workshop Talk

Approximating Submodular Functions Everywhere

Nick Harvey, Univeristy of Waterloo

Sunday, October 4, 11:30am-12:30pm

ABSTRACT

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 work, we consider the problem of approximating a 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 g such that, for every set S, g(S) approximates f(S) within a factor alpha(n) , where alpha(n)=sqrt(n+1) for rank functions of matroids and alpha(n)=O(sqrt(n) log n) 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 Omega(sqrt(n) / log n) , even for rank functions of a matroid. This is joint work with Michel Goemans (MIT), Satoru Iwata (Kyoto) and Vahab Mirrokni (Google).

Slides

Speaker Bio

Nick Harvey works on combinatorial optimization, with particular emphasis on algorithms relating to matchings and matroids. He has also worked on many theorical problems relating to peer-to-peer networks and network coding. He holds a Ph.D. in theoretical computer science from the Massachusetts Institute of Technology, and is now an assistant professor in the Department of Combinatorics and Optimization at the University of Waterloo.

< Schedule < EaGL-II homepage