The Power of Subsampling in Submodular Maximization

• 成果类型: Article
• 署名作者: Harshaw, Christopher; Kazemi, Ehsan; Feldman, Moran; Karbasi, Amin
• 署名单位: Yale University; Alphabet Inc.; Google Incorporated; University of Haifa; Yale University; Yale University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2021.1172
• 发表日期: 2022
• 页码: 1365-1393
• 关键词: approximations; algorithm; greedy

摘要

We propose subsampling as a unified algorithmic technique for submodular maximization in centralized and online settings. The idea is simple: independently sample elements from the ground set and use simple combinatorial techniques (such as greedy or local search) on these sampled elements. We show that this approach leads to optimal/state-of-the-art results despite being much simpler than existing methods. In the usual off-line setting, we present SAMPLEGREEDY, which obtains a (p + 2 + o(1))-approximation for maximizing a submodular function subject to a p-extendible system using O(n + nk/p) evaluation and feasibility queries, where k is the size of the largest feasible set. The approximation ratio improves to p + 1 and p for monotone submodular and linear objectives, respectively. In the streaming setting, we present Sample-Streaming, which obtains a (4p + 2 - o(1))-approximation for maximizing a submodular function subject to a p-matchoid using O(k) memory and O(km/p) evaluation and feasibility queries per element, and m is the number of matroids defining the p-matchoid. The approximation ratio improves to 4p for monotone submodular objectives. We empirically demonstrate the effectiveness of our algorithms on video summarization, location summarization, and movie recommendation tasks.