Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model

DOI10.1137/20M1357317OpenAlexW4297823791MaRDI QIDQ5028360

Naonori Kakimura, Yuichi Yoshida, Simon Mauras, Chien-Chung Huang

Publication date: 9 February 2022

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithminapproximabilitysubmodular function maximizationstreaming model

Mathematics Subject Classification ID

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

Related Items (4)

FPT-Algorithms for the \(\ell\) -Matchoid Problem with a Coverage Objective ⋮ Guarantees for maximization of \(k\)-submodular functions with a knapsack and a matroid constraint ⋮ On maximizing monotone or non-monotone \(k\)-submodular functions with the intersection of knapsack and matroid constraints ⋮ Semi-streaming algorithms for submodular matroid intersection

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Submodular maximization meets streaming: matchings, matroids, and more
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Multi-pass streaming algorithms for monotone submodular function maximization
• Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
• Better streaming algorithms for the maximum coverage problem
• Symmetry and Approximability of Submodular Maximization Problems
• A threshold of ln n for approximating set cover
• 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
• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• Online Submodular Maximization with Free Disposal: Randomization Beats ¼ for Partition Matroids
• 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
• 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: Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model