Guess Free Maximization of Submodular and Linear Sums

Moran Feldman

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


We consider the problem of maximizing the sum of a monotone submodular function and a linear function subject to a general solvable polytope constraint. Recently, Sviridenko et al. (Math Oper Res 42(4):1197–1218, 2017) described an algorithm for this problem whose approximation guarantee is optimal in some intuitive and formal senses. Unfortunately, this algorithm involves a guessing step which makes it less clean and significantly affects its time complexity. In this work we describe a clean alternative algorithm that uses a novel weighting technique in order to avoid the problematic guessing step while keeping the same approximation guarantee as the algorithm of Sviridenko et al. (2017). We also show that the guarantee of our algorithm becomes slightly better when the polytope is down-monotone, and that this better guarantee is tight for such polytopes.

שפה מקוריתאנגלית
עמודים (מ-עד)853-878
מספר עמודים26
כתב עתAlgorithmica
מספר גיליון3
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - מרץ 2021

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

Publisher Copyright:
© 2020, Springer Science+Business Media, LLC, part of Springer Nature.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Guess Free Maximization of Submodular and Linear Sums'. יחד הם יוצרים טביעת אצבע ייחודית.

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