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

The Taub Faculty of Computer Science Events and Talks

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: https://technion.zoom.us/j/92565691576
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.