An Optimal Streaming Algorithm for Submodular Maximization with a Cardinality Constraint

Naor Alaluf (), Alina Ene (), Moran Feldman (), Huy L. Nguyen () and Andrew Suh ()
Additional contact information
Naor Alaluf: Department of Mathematics and Computer Science, Open University of Israel, Raanana 4353701, Israel
Alina Ene: Department of Computer Science, Boston University, Boston, Massachusetts 02215
Moran Feldman: Department of Computer Science, University of Haifa, Haifa 3498838, Israel
Huy L. Nguyen: Khoury College of Computer Sciences, Northeastern University, Boston, Massachusetts 02115
Andrew Suh: Department of Computer Science, Boston University, Boston, Massachusetts 02215

Mathematics of Operations Research, 2022, vol. 47, issue 4, 2667-2690

Abstract: We study the problem of maximizing a nonmonotone submodular function subject to a cardinality constraint in the streaming model. Our main contribution is a single-pass (semi) streaming algorithm that uses roughly O ( k / ε 2 ) memory, where k is the size constraint. At the end of the stream, our algorithm postprocesses its data structure using any off-line algorithm for submodular maximization and obtains a solution whose approximation guarantee is α / ( 1 + α ) − ε , where α is the approximation of the off-line algorithm. If we use an exact (exponential time) postprocessing algorithm, this leads to 1 / 2 − ε approximation (which is nearly optimal). If we postprocess with the state-of-the-art offline approximation algorithm, whose guarantee is α = 0.385 , we obtain a 0.2779-approximation in polynomial time, improving over the previously best polynomial-time approximation of 0.1715. It is also worth mentioning that our algorithm is combinatorial and deterministic, which is rare for an algorithm for nonmonotone submodular maximization, and enjoys a fast update time of O ( ε −2 ( log k + log ( 1 + α ) ) ) per element.

Keywords: Primary: 90C27; secondary: 68W27; submodular maximization; cardinality constraint; semi-streaming algorithms (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.1224 (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:4:p:2667-2690

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 ().