The Power of Subsampling in Submodular Maximization

Christopher Harshaw (), Ehsan Kazemi (), Moran Feldman () and Amin Karbasi ()
Additional contact information
Christopher Harshaw: Department of Computer Science, Yale University, New Haven, Connecticut 06520
Ehsan Kazemi: Google, Zürich 8002, Switzerland
Moran Feldman: Department of Computer Science, University of Haifa, Haifa 3498838, Israel
Amin Karbasi: Departments of Electrical Engineering, Computer Science, Statistics & Data Science, Yale University, New Haven, Connecticut 06520

Mathematics of Operations Research, 2022, vol. 47, issue 2, 1365-1393

Abstract: 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 S ample G reedy , which obtains a ( p + 2 + o ( 1 ) ) -approximation for maximizing a submodular function subject to a p -extendible system using O ( n + n k / 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 S ample- S treaming , which obtains a ( 4 p + 2 − o ( 1 ) ) -approximation for maximizing a submodular function subject to a p -matchoid using O ( k ) memory and O ( k m / p ) evaluation and feasibility queries per element, and m is the number of matroids defining the p -matchoid. The approximation ratio improves to 4 p for monotone submodular objectives. We empirically demonstrate the effectiveness of our algorithms on video summarization, location summarization, and movie recommendation tasks.

Keywords: Primary: 68W25; secondary: 68R05; submodular maximization; subsampling; streaming algorithms; approximation algorithms; p -extendible systems; p -matchoids (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2021.1172 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:47:y:2022:i:2:p:1365-1393

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().