Submodular Maximization via Taylor Series Approximation

We then consider a class of submodular objectives that Submodular functions are set functions that exhibit a are a summation over non-linear functions of these multilinear diminishing returns property. They naturally arise in functions. Our key observation is that the polynomial many applications, including data summarization [2-4], expansions of these functions are again multilinear; facility location [5], recommendation systems [6], influence hence, compositions of multilinear functions with maximization [7], sensor placement [8], dictionary arbitrary analytic functions, that can be approximated learning [9, 10], and active learning [11]. In these problems, by a Taylor series, can be computed efficiently. A broad the goal is to maximize a submodular function range of problems, e.g., data summarization, influence subject to matroid constraints. These problems are in maximization, facility location, and cache networks (c.f.