The Taub Faculty of Computer Science Events and Talks

Motivated by applications in machine learning, such as subset selection and data summarization, we consider the problem of maximizing a monotone submodular function subject to mixed packing and covering constraints. We present a tight approximation algorithm that for any constant $\eps >0$ achieves a guarantee of $1-\nicefrac[ ]{1}{\e}-\eps$ while violating only the covering constraints by a multiplicative factor of $1-\eps$. Our algorithm is based on a novel enumeration method, which unlike previously known enumeration techniques, can handle both packing and covering constraints. We extend the above main result by additionally handling a matroid independence constraints as well as finding (approximate) pareto set optimal solutions when multiple submodular objectives are present.