| Combinatorial optimization problems are such a class of mathematical programming problems, also known as portfolio planning, which according to a goal to find out one of the most optimal solution in a given finite constraints. Combinatorial optimization is consist of a finite number of programs in order to select the objective function for optimal subset of the optimal solution. combinatorial optimization problems can be used in various fields like production and daily life, such as in the production of goods, transportation routes problem,packing problem and the work assignment problems. When the matroid theory are get into combinatorial optimization problems in the areas of research, a lot of theoretical results can be found, such as marketing problems, shortest path problem and the maximum spanning tree problem.Submodular function is a real-valued function in definition of the power set. submodular function variation is disconnected. Due to the special value of this function makes the submodular played an important role in solving optimization problems. Maximization submodulus function in combinatorial optimization is a central issue, many combinatorial optimization problems of sovling the optimal value in fact can be turned into solving the maximum value of submodular function problem.This makes the combinatorial optimization problems can be considered to be solved under the mode functions.Summed up many important issues such as maximum cut problem addressed, maximum entropy sampling problem, the maximum facility location problems and set covering problem. So for the modular function most value problem research has special theoretical and practical application value. However, solving the submodilar function is an NP- hard problem, people are constantly looking for efficient polynomial algorithm.This paper is mainly introduce the optimal value theory of solving submodular function and the the application of solving the maximum value of modular function under the greedy algorithm. We give an approximate greedy algorithm in solving any non-negative modular function under the maximum in the restriction of multiple matroids. Finally, introduced the most value problems under the function k-dimensional knapsack constraints. And various algorithms are analyzed in order to get its performance guarantee.This paper is divided into five chapters, the first chapter introduces the theory of optimization problems and greedy algorithms, and how to analyze the algorithm’s performance guarantees, and then gives the background to the study, the final task of this paper and presented to solve the problem.The second chapter reviews the concept and function of submodular, and the greedy algorithm to solve the minimum set cover problem, and gives this greedy algorithm performance guarantees.The third chapter details the approximate greedy algorithm and local search procedures in solving the die Maximization of K matroid constraints and prove approximation algorithm forThe fourth chapter describes the function of submodular maximum approximation algorithm in K-dimensional knapsack constraints, this algorithm proved an approximate solution.Chapter V of the paper conducted a comprehensive summary and outlook. Illustrates the validity and practicality. |
