Streaming algorithms for submodular function maximization

DOI10.1007/978-3-662-47672-7_26zbMATH Open1409.68340arXiv1504.08024OpenAlexW2223858906MaRDI QIDQ3448795FDOQ3448795

Authors: Chandra Chekuri, Shalmoli Gupta, Kent Quanrud 

Publication date: 27 October 2015

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

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.

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

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
• Submodular maximization meets streaming: matchings, matroids, and more
• Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Monotone Submodular Maximization over a Matroid via Non-Oblivious Local Search
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Submodular functions and optimization.
• Title not available (Why is that?)
• 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
• Submodular maximization over multiple matroids via generalized exchange properties
• Title not available (Why is that?)
• Submodular secretary problem and extensions
• Submodular function maximization via the multilinear relaxation and contention resolution schemes
• On graph problems in a semi-streaming model
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
• Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints
• Buyback problem -- approximate matroid intersection with cancellation costs
• Maximizing nonmonotone submodular functions under matroid or knapsack constraints
• Symmetry and approximability of submodular maximization problems
• From query complexity to computational complexity
• A Unified Continuous Greedy Algorithm for Submodular Maximization
• Submodular maximization meets streaming: matchings, matroids, and more
• On Multiplicative Weight Updates for Concave and Submodular Function Maximization
• Submodular Maximization with Cardinality Constraints
• Title not available (Why is that?)
• Online Submodular Maximization with Preemption

Cited In (34)

• Approximating Robust Parameterized Submodular Function Maximization in Large-Scales
• An optimal streaming algorithm for non-submodular functions maximization on the integer lattice
• Submodular maximization meets streaming: matchings, matroids, and more
• Matroid-constrained vertex cover
• Streaming submodular maximization with the chance constraint
• Budget-Feasible Mechanism Design for Non-monotone Submodular Objectives: Offline and Online
• Thresholding Methods for Streaming Submodular Maximization with a Cardinality Constraint and Its Variants
• The Power of Subsampling in Submodular Maximization
• Better streaming algorithms for the maximum coverage problem
• Approximate F_2-Sketching of Valuation Functions
• Small Space Stream Summary for Matroid Center
• Fractional Set Cover in the Streaming Model.
• Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model
• The one-way communication complexity of submodular maximization with applications to streaming and robustness
• Title not available (Why is that?)
• Современные методы математического моделирования развития гидродинамических неустойчивостей и турбулентного перемешивания
• Streaming submodular maximization under differential privacy noise
• Streaming algorithms for maximizing DR-submodular functions with \(d\)-knapsack constraints
• Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams
• 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 function maximization under \(b\)-matching, matroid, and matchoid constraints
• Non-submodular streaming maximization with minimum memory and low adaptive complexity
• An Optimal Streaming Algorithm for Submodular Maximization with a Cardinality Constraint
• Semi-streaming algorithms for submodular matroid intersection
• Semi-streaming algorithms for submodular matroid intersection
• FPT-Algorithms for the \(\ell\) -Matchoid Problem with a Coverage Objective
• Semi-Streaming Algorithms for Submodular Function Maximization Under b-Matching, Matroid, and Matchoid Constraints
• Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint
• Sequence submodular maximization meets streaming
• Multi-pass streaming algorithms for monotone submodular function maximization
• Title not available (Why is that?)
• Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
• Streaming submodular maximization under \(d\)-knapsack constraints

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)