Online submodular maximization: beating 1/2 made simple

• 成果类型: Article
• 署名作者: Buchbinder, Niv; Feldman, Moran; Filmus, Yuval; Garg, Mohit
• 署名单位: Tel Aviv University; Open University Israel; Technion Israel Institute of Technology; University of Haifa; Universita della Svizzera Italiana
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-019-01459-z
• 发表日期: 2020
• 页码: 149-169

摘要

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 of1-1/e.