Streaming Algorithms for Submodular Function Maximization
From MaRDI portal
Publication:3448795
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
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