Timezone: »

 
Poster
Optimization for Approximate Submodularity
Yaron Singer · Avinatan Hassidim

Wed Dec 05 02:00 PM -- 04:00 PM (PST) @ Room 210 #35
in Wed Poster Session B »

We consider the problem of maximizing a submodular function when given access to its approximate version. Submodular functions are heavily studied in a wide variety of disciplines, since they are used to model many real world phenomena, and are amenable to optimization. However, there are many cases in which the phenomena we observe is only approximately submodular and the approximation guarantees cease to hold. We describe a technique which we call the sampled mean approximation that yields strong guarantees for maximization of submodular functions from approximate surrogates under cardinality and intersection of matroid constraints. In particular, we show tight guarantees for maximization under a cardinality constraint and 1/(1+P) approximation under intersection of P matroids.

Keywords: Submodular Optimization
[ Paper] 

Author Information

Yaron Singer (Harvard University)
Avinatan Hassidim (Bar Ilan University)

More from the Same Authors