Improved Fully Dynamic Submodular Maximization Under Matroid Constraints

This paper studies submodular maximization over matroids in the fully dynamic setting, where elements of an underlying ground set undergo sequential insertions and deletions. The goal is to maintain an approximate optimal solution for the current element set with a low amortized update time. For monotone submodular functions, we propose a dynamic algorithm achieving a (0.3178 - epsilon)-approximation using O-tilde(k^3) expected amortized queries, where k is the rank of the matroid constraint. Furthermore, we extend our approach to the non-monotone submodular maximization setting, obtaining a (0.1921 - epsilon)-approximation with the same update complexity. Both algorithms improve upon the best known approximation guarantees, which are (0.25 - epsilon) for the monotone case and (0.0932 - epsilon) for the non-monotone case.

Authors

• Yiwei Gao State Key Lab of Processors, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China School of Computer Science and Technology, University of Chinese Academy of Sciences, Beijing 100049, China
• Jialin Zhang Nanjing University of Aeronautics and Astronautics
• Zhijie Zhang Fuzhou University

Keywords

No keywords are indexed for this paper.