Online submodular maximization: beating 1/2 made simple

Niv Buchbinder, Moran Feldman, Yuval Filmus, Mohit Garg

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


The Submodular Welfare Maximization problem (SWM) captures an important subclass of combinatorial auctions and has been studied extensively. In particular, it has been studied in a natural online setting in which items arrive one-by-one and should be allocated irrevocably upon arrival. For this setting, Korula et al. (SIAM J Comput 47(3):1056–1086, 2018) were able to show that the greedy algorithm is 0.5052-competitive when the items arrive in a uniformly random order. Unfortunately, however, their proof is very long and involved. In this work, we present an (arguably) much simpler analysis of the same algorithm that provides a slightly better guarantee of 0.5096-competitiveness. Moreover, this analysis applies also to a generalization of online SWM in which the sets defining a (simple) partition matroid arrive online in a uniformly random order, and we would like to maximize a monotone submodular function subject to this matroid. Furthermore, for this more general problem, we prove an upper bound of 0.574 on the competitive ratio of the greedy algorithm, ruling out the possibility that the competitiveness of this natural algorithm matches the optimal offline approximation ratio of 1 - 1 / e.

שפה מקוריתאנגלית
עמודים (מ-עד)149-169
מספר עמודים21
כתב עתMathematical Programming
מספר גיליון1-2
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 1 ספט׳ 2020

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

Publisher Copyright:
© 2020, Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Online submodular maximization: beating 1/2 made simple'. יחד הם יוצרים טביעת אצבע ייחודית.

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