The power of subsampling in submodular maximization

DOI10.1287/MOOR.2021.1172MaRDI QIDQ5085145zbMATH OpenOpenAlexFDO

Authors Christopher Harshaw, E. Kazemi, Moran Feldman, Amin Karbasi

Publication date 27 June 2022

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2104.02772

zbMATH Keywords

\(p\)-extendible systems\(p\)-matchoidsapproximation algorithmsstreaming algorithmssubmodular maximizationsubsampling

Mathematics Subject Classification ID

Randomized algorithms (68W20) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27) Combinatorial optimization (90C27)

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 offline 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 SampleStreaming, 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, where $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.

Recommendations

• An Optimal Streaming Algorithm for Submodular Maximization with a Cardinality Constraint
• Fast algorithms for maximizing submodular functions
• Distributed submodular maximization
• Streaming algorithms for robust submodular maximization
• A survey on streaming algorithms for maximizing submodular functions

Cites work

• A \(\frac{(k+3)}{2}\)-approximation algorithm for monotone submodular \(k\)-set packing and general \(k\)-exchange systems
• A Unified Continuous Greedy Algorithm for Submodular Maximization
• An analysis of approximations for maximizing submodular set functions—I
• An Exact Algorithm for Maximum Entropy Sampling
• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• Buyback problem -- approximate matroid intersection with cancellation costs
• Constrained submodular maximization via a nonsymmetric technique
• Determinantal point processes for machine learning
• Deterministic Algorithms for Submodular Maximization Problems
• Distributed submodular maximization
• Exact matrix completion via convex optimization
• Fast algorithms for maximizing submodular functions
• Greedy in Approximation Algorithms
• scientific article; zbMATH DE number 3635849 (Why is no real title available?)
• Improved approximations for k-exchange systems (extended abstract)
• Matrix completion and low-rank SVD via fast alternating least squares
• Maximizing a monotone submodular function subject to a matroid constraint
• Maximizing nonmonotone submodular functions under matroid or knapsack constraints
• Online submodular maximization with preemption
• Online submodular welfare maximization: greedy beats 1/2 in random order
• Streaming algorithms for submodular function maximization
• Submodular maximization by simulated annealing
• Submodular maximization over multiple matroids via generalized exchange properties
• Submodular maximization with cardinality constraints
• Symmetry and approximability of submodular maximization problems
• The coincidence approach to stochastic point processes

Cited in

(9)

• A unifying look at sequence submodularity
• Online risk-averse submodular maximization
• Streaming adaptive submodular maximization
• Randomized composable core-sets for distributed submodular maximization
• Distributed submodular maximization
• Submodular Approximation: Sampling-based Algorithms and Lower Bounds
• Sampling subproblems of heterogeneous Max-Cut problems and approximation algorithms
• The one-way communication complexity of submodular maximization with applications to streaming and robustness
• From global to query-dependent: summarization of large hierarchical DAGs

This page was built for publication: The power of subsampling in submodular maximization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5085145)