Streaming Algorithms for Submodular Function Maximization

2015/04/29 by Chandra Chekuri, Chekuri, Chandra, Shalmoli Gupta +3 · 3 citations
Computer Science · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Privacy-Preserving Technologies in Data

paper · pdf · doi:10.48550/arxiv.1504.08024

openalex publication_date 2015/04/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider the problem of maximizing a nonnegative submodular set function f:2^N → ℝ⁺ subject to a p-matchoid constraint in the single-pass streaming setting. Previous work in this context has considered streaming algorithms for modular functions and monotone submodular functions. The main result is for submodular functions that are \em non-monotone. We describe deterministic and randomized algorithms that obtain a Ω((1)/(p))-approximation using O(k log k)-space, where k is an upper bound on the cardinality of the desired set. The model assumes value oracle access to f and membership oracles for the matroids defining the p-matchoid constraint.

Cited by

• OptMap: Geometric Map Distillation via Submodular Maximization
• Stream Clipper: Scalable Submodular Maximization on Stream
• A Two-Pass Lower Bound for Semi-Streaming Maximum Matching

Related

• Improved Multi-Pass Streaming Algorithms for Submodular Maximization with Matroid Constraints
• Streaming Submodular Maximization under Matroid Constraints
• Semi-Streaming Algorithms for Submodular Function Maximization Under b-Matching, Matroid, and Matchoid Constraints
• Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model
• Streaming Submodular Maximization under a k-Set System Constraint