Approximation Algorithms For Submodular And Nonsubmodular Maximization Over Matroid Constraints

For the set function,its submodularity is equivalent to the economic concept of the law of diminishing marginal returns.The law of diminishing marginal returns refers to the phenomenon that the benefit of adding one unit of the factor will decrease when the input of the production factor increases to a certain level in a short-term production process.Submodular optimization has important research value from both theoretical and practical perspectives.In theory,many classic combinatorial optimization problems can be regarded as submodular maximization or submodular minimization,such as facility location,generalized distribution,max cut,max directed cut,max k cover,and max bisection etc.In real life,it can be found that various application scenarios of submodular problems and their deformation problems from industrial engineering,computer science,finance,economics,operations research,machine learning and many other fields.This doctoral dissertation focuses on submodular maximization problems with matroid constraints and related deformation problems.It consists of the following four works:deterministic algorithms study of monotone submodular maximization problem with matroid constraints;maximization of the sum of a non-monotone submodular and modular functions subject to a down-closed family of subsets;non-monotone private submodular maximization over a down-closed family of subsets;adaptive algorithms study of monotone non-submodular maximization under matroid constraints.Since the above problems are all NP-hard problems,this thesis designs approximation algorithms with rigorous and complete analysis processes for obtaining the approximation guarantee.The technical route of the algorithms takes the greedy approaches as the main technique,and the threshold methods as the second.Besides,the results can be got with the help of some important concepts and properties such as multilinear extension,Lovász extension and contracting matroids etc.Specifically,the main achievements of this thesis are as follows:The second chapter is about the study of the research on deterministic approximation algorithms for monotone submodular maximization with matroid constraints.Matroid constraints are a common constraint for submodular maximization problems,and it is a useful combinatorial structure that generalizes the linear independence in linear algebra to the set theory.A matrod can be regarded as a two-tuple structure composed of a ground set and an independent system.The independent system is a subset family of the given ground set,which also satisfies the down-closed property and augmentation property.The importance of the matroids lies in that it provides a concise and unified abstract treatment for the correlation between linear algebra and graph theory,which enables the theory of matroids to be successfully and widely used in combinatorial optimization and network optimization.For this problem,the thesis designs a greedy approximation algorithm with the help of the properties of contracted matroids.The algorithm yields an parameterized approximation guanrantee with 1+hc(y)+Δ·[3+c-(2+c)y-(1+c)hc(y)]/2+c+(1+c)(1-y),where c ∈[0,1]is the curvature of the set function,y ∈[0,1]is a hyper-parameter and hc(y)(?)1-(1-y)1+c/1+c is the denoted function.Our results generalize the best deterministic approximation algorithm for this problem.The third chapter is about the study of the research on the maximization of the sum of a non-monotone submodular and modular functions subject to a down-closed family of subsets.This thesis designs a measured continuous greedy with adaptive weights algorithm.The algorithm first gives the approximation guarantee with submodular term as 1/e,and the modular term as β-e/e(β-1),where β ∈[0,1)∪(1,∞]is a parameter,which describes the ratio of non-negative parts and negative parts of the optimal modular function value.Moreover,for the original problem,the thesis gives a hardness result.The thesis proves that there exists no polynomial-time algorithm with an approximation ratio better than 0.478.In addition,The above algorithm is also suitable for the monotone submodular functions.In this setting,the approximate ratio is 1-1/e,which is the tight bound of the problem that the thesis studies.The fourth chapter is about the study of the research on non-monotone private submodular maximization over a down-closed family of subsets.The thesis designs a O((?))-private algorithm with the concept differential privacy and the powerful technique exponential mechanism.For the relaxation problem,the thesis obtains an(Te-T-O(1))-approximation algorithm with O(2Δ/(?)n4)additive error for privacy,where T ∈[0,1]is the stopping time of the algorithm,and Δ is the sensitivity of the set function associated with a given sensitive dataset.For a certain matroid constraint,the thesis can get a discrete solution with the same approximation ratio by a lossless rounding technique called pipage rounding.In addition,our algorithm can also be applied to the case where the submodular function is monotone with(1-e-T-O(1))guarantee.The fifth chapter is about the study of the research on adaptive algorithms study of monotone non-submodular maximization under matroid constraints.The thesis firstly designs an adaptive algorithm with sublinear adaptivity.The adaptivity of the algorithm is O(log n log(r)),where n is the size of the given ground set,r is the rank of the matroid.The algorithm outputs an fractional result with(1-e-γ2-O((?)))approximation guarantee and an integer solution can be obtained by using the CR scheme rounding method at the guarantee cost of γ(1-1/e).