Fully dynamic submodular maximization over matroids

DOI10.1145/3698397MaRDI QIDQ7023526zbMATH OpenFDO

Authors Paul Dütting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard, Morteza Zadimoghaddam

Publication date 21 February 2025

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1145/3698397

zbMATH Keywords

fully dynamic algorithmsmatroidssubmodular maximization

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Data structures (68P05) Combinatorics in computer science (68R05) Randomized algorithms (68W20) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Cites work

• A threshold of ln n for approximating set cover
• Adaptive submodularity: theory and applications in active learning and stochastic optimization
• Dynamic algorithms for matroid submodular maximization
• Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint
• scientific article; zbMATH DE number 3580314 (Why is no real title available?)
• scientific article; zbMATH DE number 3635849 (Why is no real title available?)
• Maximizing a monotone submodular function subject to a matroid constraint
• On the complexity of dynamic submodular maximization
• Robust monotone submodular function maximization
• Streaming algorithms for submodular function maximization
• Streaming submodular maximization under matroid constraints
• Submodular maximization meets streaming: matchings, matroids, and more
• The one-way communication complexity of submodular maximization with applications to streaming and robustness
• Towards nearly-linear time algorithms for submodular maximization with a matroid constraint

Cited in

(2)

• Submodular maximization subject to a knapsack constraint: combinatorial algorithms with near-optimal adaptive complexity
• Deletion robust non-monotone submodular maximization over matroids

This page was built for publication: Fully dynamic submodular maximization over matroids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7023526)