The power of subsampling in submodular maximization

DOI10.1287/MOOR.2021.1172zbMATH Open1492.68141arXiv2104.02772OpenAlexW3206123738MaRDI QIDQ5085145FDOQ5085145

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)

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.

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

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

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)

Cites Work

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

Cited In (7)

• A unifying look at sequence submodularity
• Randomized composable core-sets for distributed submodular maximization
• Submodular Approximation: Sampling-based Algorithms and Lower Bounds
• Distributed submodular maximization
• Streaming adaptive submodular maximization
• Sampling subproblems of heterogeneous Max-Cut problems and approximation algorithms
• 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)