דלג לתוכן (מקש קיצור 's')
Logo of Technion
Logo of CS Department
אירועים

אירועים

A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints
event speaker icon
אייל מזרחי , הרצאה סמינריונית למגיסטר
event date icon
יום ראשון, 29.11.2020, 11:30
event location icon
הרצאה באמצעות זום: https://technion.zoom.us/j/92565691576
event speaker icon
מנחה:  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.
[בחזרה לאינדקס האירועים]