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

subsamplingapproximation algorithmsstreaming algorithmssubmodular maximization\(p\)-extendible systems\(p\)-matchoids

Mathematics Subject Classification ID

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

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

• scientific article; zbMATH DE number 3635849 (Why is no real title available?)
• A Unified Continuous Greedy Algorithm for Submodular Maximization
• A \(\frac{(k+3)}{2}\)-approximation algorithm for monotone submodular \(k\)-set packing and general \(k\)-exchange systems
• An Exact Algorithm for Maximum Entropy Sampling
• An analysis of approximations for maximizing submodular set functions—I
• 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
• 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

(7)

• Sampling subproblems of heterogeneous Max-Cut problems and approximation algorithms
• Randomized composable core-sets for distributed submodular maximization
• A unifying look at sequence submodularity
• Submodular Approximation: Sampling-based Algorithms and Lower Bounds
• Streaming adaptive submodular maximization
• Distributed submodular maximization
• Online risk-averse submodular maximization

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)