Multi-pass streaming algorithms for monotone submodular function maximization

DOI10.1007/s00224-021-10065-6OpenAlexW3213622323MaRDI QIDQ2075395

Naonori Kakimura, Chien-Chung Huang

Publication date: 14 February 2022

Published in: Theory of Computing Systems (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmsstreaming algorithmssubmodular function maximization

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Mathematical programming (90Cxx) Theory of computing (68Qxx)

Related Items (1)

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
• Unnamed Item
• Submodular maximization meets streaming: matchings, matroids, and more
• A note on maximizing a submodular set function subject to a knapsack constraint
• Linear programming in the semi-streaming model with application to the maximum matching problem
• Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
• Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
• Streaming Algorithms for Submodular Function Maximization
• Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
• An analysis of approximations for maximizing submodular set functions—I
• Online Submodular Maximization with Free Disposal: Randomization Beats ¼ for Partition Matroids
• Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams
• A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
• Online Submodular Maximization Problem with Vector Packing Constraint.
• Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes
• The one-way communication complexity of submodular maximization with applications to streaming and robustness
• The adaptive complexity of maximizing a submodular function
• Maximizing a Monotone Submodular Function with a Bounded Curvature under a Knapsack Constraint
• Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time
• An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
• Submodular Function Maximization in Parallel via the Multilinear Relaxation
• Fast algorithms for maximizing submodular functions
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Monotone Submodular Maximization over a Matroid via Non-Oblivious Local Search
• Submodular Maximization over Multiple Matroids via Generalized Exchange Properties
• Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint

This page was built for publication: Multi-pass streaming algorithms for monotone submodular function maximization