Local Search Algorithms And Performance Guarantees For Minimizing Supermodular Function Subject To A Cardidity Constraint

Combinatorial optimization is an important branch of operational research, which decide to find the optimal screening, grouping, sorting, Etc. of discrete problem by mathematical method. The research field of this subject involves the study of informa-tion technology, economic management, industrial engineering, transport, communication networks, and other areas. Unfortunately, the vast majority of combinatorial optimization problems are the NP-hard problems, that is, there is no effective polynomial-time algorithm for them in most cases. Therefore, people focus on finding polynomial approximation algorithm to find approximate solutions. Local search algorithm is one of the most simple, flexible and effective kind. In solving combinatorial optimization problems, local search algorithm is to limit the search space of a certain type within the solution space. 60-70 in the 20th century, Lin and Kemighan have developed the classic local search algorithm in the range of technologies in solving Traveling Salesman problem and Parting problem. Following the birth of local search algorithm in the industry, it not only has important application in optimization problems but also has many research results in the complexity of the algorithm in theory.Supermodular function is a kind of real function that defines on power set of the limited set (or lattices). The biggest difference between supermodular function and the general real function is that the variables of supermodular function are discrete. This distinction is made supermodular function has played a very important role in combinatorial optimization. On the one hand, the proposition of supermodular function has important application in combinatorial optimization. On the other hand, many combinatorial optimization problems can be solved as the Minimizing (Maximizing) Supermodular problem, such as the simple plant location problem, k-Median, the generalized transportation problem, set covering and so on. Therefore, the research of supermodular function is very theoretical and applied value. However, the minimization (maximization) of a supermodular function is known to be NP-hard. Therefore, people committed to finding effective polynomial approximation algorithm. Sometimes even to address the special case.In this paper, we briefly introduce the basic principles and development situation of local search algorithm, and then present a number of propositions of supermodular func- tion. Finally, use local search algorithm to solve the minimizing supermodular function subject to a cardidity constraint.The full text is divided into four chapters, Chapter 1 firstly outlines the basic concept of combinatorial optimization problems and the classification of problem, and then presents to two different methods to solving combinatorial optimization problems, namely, accurate algorithms and approximation algorithms, the final arrangements on the content of this paper.Chapter 2 Summaries research situation of local search algorithm and its extensive application in combination optimization. Introductions basic principle and some basic concepts of local search algorithm. Gives a general description as well as improving methods. Finally, proves that the improved local search algorithm is polynomial time approximation algorithm.The third chapter describes supermodular function touch on the basic concepts and propositions, two specific examples are given, Through the relevant literature, a brief overview is given of the current research on the supermodular function as well as their important applications in operations research, applied mathematics and computer science.Chapter IV presents local search algorithm for minimizing supermodular function subject to a cardidity constraint, and theoretically analyzed the performance guarantees of the algorithm, which show that the algorithm is effective and practical. In this paper, we consider the following two situations:(1)we presents local search algorithm and performance guarantees for minimizing non-negative and non-increasing supermodular function subject to a cardidity constraint. The results have being compared with that of has been obtained, and show the advantages and deficiencies.(2) On the basis of (1),we gives local search algorithm and performance guarantees for minimizing non-negative and non-decreasing supermodular function subject to a cardidity constraint.