Research On Submodular Maximization Algorithms With Low-Time Complexity

As a classical optimization problem,submodular maximization has a wide range of implications and applications in computer science,artificial intelligence,big data,operational optimization,game theory,financial investment,etc.In the early stages of studying algorithms for submodular maximization,due to the limited amount of data and the simple applications,researchers were primarily interested in how to improve the approximation guarantees of algorithms as much as possible,thus neglecting the time complexity of algorithms.However,with the advent of the big data era,the amount of data continues to grow and the applications become more and more complex,which makes it difficult for classical algorithms with near-optimal approximation ratios to satisfy practical requirements due to the unrealistically steep time complexity.Therefore,in this dissertation,we will focus on submodular maximization algorithms with lowtime complexity and investigate how to enhance the approximation guarantees while ensuring the low-time complexity,or reduce the time complexity while maintaining the approximation guarantees.This dissertation consists of three main parts,which are illustrated below.(1)Research on monotone submodular maximization algorithms for revenue maximization in social advertising.In this part,we mainly consider how to select suitable seed users from the social network to promote products under the setting of multi-advertiser,so as to maximize the advertising revenue of the social platform.The problem can be modeled as a monotone submodular maximization problem with a partition matroid and multiple submodular knapsack constraints.Since the submodular maximization problem is NP-hard and the influence estimation of seed users is#Phard,the problem is highly challenging.To address this problem,under the assumption of the existence of an influence oracle,we first design a novel ideal algorithm with constant approximation ratio by using greedy threshold selection and binary search strategy.Then,we propose a novel uniform sampling method for estimating the influence of seed users.Combining the uniform sampling method with the ideal algorithm,we finally design a practical algorithm.Theoretical analysis demonstrates that the practical algorithm can achieve a near-constant approximation ratio with the probability of 1-δ,where δ∈(0,1)is an arbitrarily small parameter.Moreover,extensive experimental results show that the practical algorithm significantly outperforms existing algorithms in terms of advertising revenue,seed selection cost,budget utilization,and scalability.(2)Research on monotone submodular maximization algorithms for task assignment with group fairness for crowdsourcing.In this part,we mainly study the task assignment with group fairness for crowdsourcing.Based on the fair budget allocation principle,we first provide a well-designed group fairness constraint model that can be incorporated into the task assignment problem,making any algorithm product an assignment with group fairness,even for a random algorithm.The effectiveness of the group fairness constraint model has been well demonstrated experimentally.Combining with the group fairness constraint model,we investigate two classical task assignment problems for crowdsourcing and show that they are essentially monotone submodular maximization problems subject to a knapsack and multiple partition matroid constraints.To address them,we design two algorithms,O2-GE and M2-GE,based on density threshold selection and candidate solution augmentation strategies.The O2-GE algorithm mainly serves in the scenario of "One-task-to-One-worker",and can return a solution with an approximation ratio of near-3.4 in near-linear running time,while the M2-GE algorithm is mainly used for the scenario of "Many-tasks-to-Many-workers",and can achieve the approximation ratio of near-4.3 using near-linear running time.Experimental results show that both algorithms are state-of-the-art in terms of utility,running time,and group fairness.(3)Research on non-monontone submodular maximization algorithms for data summarization.In this part,we mainly focus on two important types of submodular data summarization problems:SMM and SMKM.The essence of the SMM problem is a non-monotone submodular maximization subject to a matroid constraint,whose application scenarios include social network monitoring,virus marketing,etc.To solve it,we design a fast algorithm with approximation ratio 4 and time complexity O(nr)based on simultaneous greedy selection,where n is the size of the dataset and r is the maximum size of a feasible solution.To further improve the running efficiency,we combine the threshold selection strategy to obtain an accelerated algorithm that achieves time complexity O(n log r)and approximation ratio near-4.The theoretical model for the SMKM problem is a non-monotone submodular maximization problem with knapsack and matroid constraints,whose application scenarios include image summarization,movie recommendation,revenue maximization on social networks,etc.To address it,we propose a fast algorithm with approximation ratio 8 and time complexity O(nr log n),based on the novel combination of simultaneous greedy selection and density threshold selection.Moreover,for the particular scenario of partition matroid constraint,we design a fast algorithm with an approximate ratio close to 7.2 and time complexity O(nr log n)by incorporating novel candidate solution augmentation techniques.Experimental results demonstrate the state-of-the-art of the above algorithms in terms of utility and running time.