Local Search Algorithm for Solving Maximizing Submodular Set Function

This paper presents a local search algorithm which maximizes a nondecreasing submodular set function and discusses its performance guarantee as well.The basic idea lies in which each iterative algorithm is always in the neighborhood sets of the current approximate solution,solving a set which maximize the objective function is a new approximate set.Analysis shows that the algorithm is a polynomial time algorithm.