New approximation algorithm for maximizing submodular set function

Targeted at difficulties due to an effective algorithm for the problem of maximizing a submodular set function classified as NP-hards,this paper gives a new approximation algorithm for maximizing submodular set functions by means of probability distribution.The paper proves that the performance guarantee of this algorithm is 1/3.The effect of this algorithm is illustrated by using a combinatorial optimization problem.This study provides a new idea for solving maximizing submodular set function.