Streaming algorithms for submodular function maximization

DOI10.1007/978-3-662-47672-7_26MaRDI QIDQ3448795zbMATH OpenOpenAlexFDO

Authors Chandra Chekuri, Shalmoli Gupta, Kent Quanrud

Publication date 27 October 2015

Published in Automata, Languages, and Programming (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

Abstract: We consider the problem of maximizing a nonnegative submodular set function $f:2^{mathcalN}ightarrowmathbb{R}^{+}$ 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 $Omega(frac1p)$-approximation using $O(klogk)$-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.

Recommendations

• An Optimal Streaming Algorithm for Submodular Maximization with a Cardinality Constraint
• Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
• Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
• Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint

Cites work

• A Unified Continuous Greedy Algorithm for Submodular Maximization
• An analysis of approximations for maximizing submodular set functions—I
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints
• Buyback problem -- approximate matroid intersection with cancellation costs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Fast algorithms for maximizing submodular functions
• From query complexity to computational complexity
• scientific article; zbMATH DE number 6474901 (Why is no real title available?)
• scientific article; zbMATH DE number 3635849 (Why is no real title available?)
• Improved approximations for k-exchange systems (extended abstract)
• Matroids, secretary problems, and online mechanisms
• Maximizing a monotone submodular function subject to a matroid constraint
• Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
• Maximizing nonmonotone submodular functions under matroid or knapsack constraints
• Monotone submodular maximization over a matroid via non-oblivious local search
• On graph problems in a semi-streaming model
• On multiplicative weight updates for concave and submodular function maximization
• Online submodular maximization with preemption
• Solving packing integer programs via randomized rounding with alterations
• Submodular function maximization via the multilinear relaxation and contention resolution schemes
• Submodular functions and optimization.
• Submodular maximization over multiple matroids via generalized exchange properties
• Submodular maximization with cardinality constraints
• Submodular secretary problem and extensions
• Symmetry and approximability of submodular maximization problems

Cited in

(44)

• Non-submodular streaming maximization with minimum memory and low adaptive complexity
• Multi-pass streaming algorithms for monotone submodular function maximization
• Bicriteria streaming algorithms to balance gain and cost with cardinality constraint
• Streaming submodular maximization under differential privacy noise
• Streaming algorithms for maximizing DR-submodular functions with d-knapsack constraints
• Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
• Non-submodular maximization on massive data streams
• Better streaming algorithms for the maximum coverage problem
• An optimal streaming algorithm for non-submodular functions maximization on the integer lattice
• Streaming submodular maximization under \(d\)-knapsack constraints
• scientific article; zbMATH DE number 6905172 (Why is no real title available?)
• Fractional set cover in the streaming model
• Maximum matching in two, three, and a few more passes over graph streams
• Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model
• The power of subsampling in submodular maximization
• Deterministic algorithms for maximum matching on general graphs in the semi-streaming model
• Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint
• Modern methods of mathematical modeling of the development of hydrodynamic instabilities and turbulent mixing
• A survey on streaming algorithms for maximizing submodular functions
• The one-way communication complexity of submodular maximization with applications to streaming and robustness
• Approximating robust parameterized submodular function maximization in large-scales
• Thresholding Methods for Streaming Submodular Maximization with a Cardinality Constraint and Its Variants
• Budget-feasible mechanism design for non-monotone submodular objectives: offline and online
• An Optimal Streaming Algorithm for Submodular Maximization with a Cardinality Constraint
• Small Space Stream Summary for Matroid Center
• Approximate F₂-Sketching of Valuation Functions
• Sequence submodular maximization meets streaming
• Semi-streaming algorithms for submodular matroid intersection
• Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
• Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
• Semi-streaming algorithms for submodular matroid intersection
• Semi-Streaming Algorithms for Submodular Function Maximization Under b-Matching, Matroid, and Matchoid Constraints
• FPT-Algorithms for the \(\ell\) -Matchoid Problem with a Coverage Objective
• Matroid-constrained vertex cover
• Streaming submodular maximization with the chance constraint
• Semi-streaming algorithms for submodular function maximization under \(b\)-matching, matroid, and matchoid constraints
• Optimal streaming algorithms for submodular maximization with cardinality constraints
• Dynamic algorithms for submodular maximization with a p-matchoid constraint
• Fair maximization of monotone submodular functions in data streams
• Submodular maximization subject to matroid intersection on the fly
• Fully dynamic submodular maximization over matroids
• Maximum coverage in the data stream model: parameterized and generalized
• Streaming algorithms for maximizing k-submodular functions under a partition matroid constraint
• Streaming algorithms for robust submodular maximization

This page was built for publication: Streaming algorithms for submodular function maximization

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