Skip to content (access key 's')
Logo of Technion
Logo of CS Department


A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints
event speaker icon
Eyal Mizrachi, M.Sc. Thesis Seminar
event date icon
Sunday, 29.11.2020, 11:30
event location icon
Zoom Lecture:
event speaker icon
Advisor:  Prof. Roy Schwartz
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.
[Back to the index of events]