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
مستوى الصوت183
رقم الإصدار1-2
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 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'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا