Research on Submodular Maximization Algorithm of Viral Marketing Data Abstract Extraction based on SMM Matroid Constraints

The essence of SMM problem is a non-monotone submodular maximization problem with a single matroid constraint, and its application scenarios include viral marketing. To solve this problem, a fast algorithm with an approximate ratio of 4 and a time complexity of O(nr) is designed using the synchronous greedy selection strategy, where n represents the size of the input data and r represents the size of the maximum feasible solution. The experimental results show the superiority of the above algorithm in data summarization efficiency and running time.