Constrained submodular maximization via a nonsymmetric technique

Niv Buchbinder, Moran Feldman

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים


The study of combinatorial optimization problems with submodular objectives has attracted much attention in recent years. Such problems are important in both theory and practice because their objective functions are very general. Obtaining further improvements for many submodular maximization problems boils down to finding better algorithms for optimizing a relaxation of them known as the multilinear extension. In this work, we present an algorithm for optimizing the multilinear relaxation whose guarantee improves over the guarantee of the best previous algorithm (by Ene and Nguyen). Moreover, our algorithm is based on a new technique that is, arguably, simpler and more natural for the problem at hand. In a nutshell, previous algorithms for this problem rely on symmetry properties that are natural only in the absence of a constraint. Our technique avoids the need to resort to such properties, and thus seems to be a better fit for constrained problems.

שפה מקוריתאנגלית
עמודים (מ-עד)988-1005
מספר עמודים18
כתב עתMathematics of Operations Research
מספר גיליון3
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2019

הערה ביבליוגרפית

Publisher Copyright:
© 2019 INFORMS

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Constrained submodular maximization via a nonsymmetric technique'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי