Approximation Algorithm And Performance Guarantee Of Solving The Maximization Of Submodular Function Under D-knapsack Constraints

Combinatorial optimization (also known as discrete optimization), is an active area ofapplied mathematics, It combines combinatorial mathematics, linear programming withalgorithm theory techniques to solve optimization problems on discrete structures. It is animportant branch of operations research in the combinatorial optimization, the study of theissues involves in economic management, logistics management, industrial engineering,transportation, computer science and information technology, communication and networktechnology, cybernetics and military operations research and many fields.0-1knapsackproblem, the multidimensional knapsack problem and the traveling salesman problemdiscussed in this article, are some basic problems of the combinatorial optimization.However, the concept of the submodular function has been proposed in the19th century,when the Edgworth and Pareto mainly advocate of this concept. In the combinatorialoptimization problems, many of the specific problems of the objective function contain thenature of submodular function. Therefore, the submodular function has a very important roleto solve the problem of combinatorial optimization. The other hand, the nature of submodularfunction has good properties in optimization algorithm design, and has a very important rolein theoretical calculation scientific fields. The Maximization of submodular function hasimportant theoretical significance and practical value, has been many theoretical studiesscholars studied extensively, also made many important achievements.This article briefly describes the theory of combinatorial optimization, combinatorialoptimization outline, definition and problem instance. Algorithm outline, the complexity ofalgorithm，the complexity of combinatorial optimization problem, and combinatorialoptimization problem complexity classified. For most combinatorial optimization problemsare TVP-hard problem, generally do not have a very good and effective method for solvingthem, particularly polynomial time algorithm. Therefore, people retreat followed for the sakeof the main go looking for solving such problems is relatively approximation algorithm. Manyresearch focused on the design of what kind of algorithm，so the algorithm design has arelatively good performance guarantees, and thus more effective solution to life combinatorialoptimization problem. The article describes the basic principles of several commonly usedalgorithms, in particular, the basic principles of the greedy algorithm, combined with thecharacteristics of the knapsack problem. Knapsack problem is with the relationship ofsubmodular function, followed by the concept of submodula function and its basic nature.Finally, we make use of a greedy algorithm to solve the d-Knapsack Problem and itsperformance guarantee. The paper is divided into five chapters, the first chapter outlines thecombinatorial optimization problem and its basic concepts, and then gives some examples of combinatorial optimization problems, the research background, last given this task of thepaper. The second chapter reviews the complexity of the algorithm complexity of its problems,the greedy algorithm basic principles and the algorithm is described and its background of theresearch, widely used in combinatorial optimization problems. The third chapter describes theapproximation algorithm and its performance guarantee, introduced several commonalgorithms, as well as to ensure the introduction of the performance guarantees of thealgorithm. The fourth chapter introduces the concept of submodular function and its basicproperties. The fifth chapter gives an algorithm of the d-Knapsack Problem and solves it，andto analyze performance guarantees of the algorithm from theoretical and its rationality.