Streaming Algorithms for Submodular Function Maximization

DOI10.1007/978-3-662-47672-7_26zbMath1409.68340arXiv1504.08024OpenAlexW2223858906MaRDI QIDQ3448795

Chandra Chekuri, Kent Quanrud, Shalmoli Gupta

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

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

Related Items (21)

The Power of Subsampling in Submodular Maximization ⋮ Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint ⋮ FPT-Algorithms for the \(\ell\) -Matchoid Problem with a Coverage Objective ⋮ Matroid-constrained vertex cover ⋮ Streaming submodular maximization with the chance constraint ⋮ Современные методы математического моделирования развития гидродинамических неустойчивостей и турбулентного перемешивания ⋮ Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams ⋮ Fractional Set Cover in the Streaming Model. ⋮ Small Space Stream Summary for Matroid Center ⋮ Approximate F_2-Sketching of Valuation Functions ⋮ Approximating Robust Parameterized Submodular Function Maximization in Large-Scales ⋮ Unnamed Item ⋮ Non-submodular streaming maximization with minimum memory and low adaptive complexity ⋮ Sequence submodular maximization meets streaming ⋮ Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint ⋮ Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint ⋮ Multi-pass streaming algorithms for monotone submodular function maximization ⋮ Better streaming algorithms for the maximum coverage problem ⋮ Budget-Feasible Mechanism Design for Non-monotone Submodular Objectives: Offline and Online ⋮ An Optimal Streaming Algorithm for Submodular Maximization with a Cardinality Constraint ⋮ Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Submodular maximization meets streaming: matchings, matroids, and more
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Submodular functions and optimization.
• On graph problems in a semi-streaming model
• Symmetry and Approximability of Submodular Maximization Problems
• Submodular secretary problem and extensions
• On Multiplicative Weight Updates for Concave and Submodular Function Maximization
• Buyback Problem - Approximate Matroid Intersection with Cancellation Costs
• Maximizing Nonmonotone Submodular Functions under Matroid or Knapsack Constraints
• Improved Approximations for k-Exchange Systems
• Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
• An analysis of approximations for maximizing submodular set functions—I
• Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints
• Online Submodular Maximization with Preemption
• Submodular Maximization with Cardinality Constraints
• Fast algorithms for maximizing submodular functions
• From query complexity to computational complexity
• Submodular function maximization via the multilinear relaxation and contention resolution schemes
• Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Monotone Submodular Maximization over a Matroid via Non-Oblivious Local Search
• A Unified Continuous Greedy Algorithm for Submodular Maximization
• Submodular Maximization over Multiple Matroids via Generalized Exchange Properties

This page was built for publication: Streaming Algorithms for Submodular Function Maximization