Study On Some Partial Inverse Maximum Spanning Tree Problems

Given a combinatorial optimization problem,its inverse problem is to make a given feasible solution to be optimal by modifying the weight function and minimizes the difference of the two weight functions.The partial inverse combinatorial optimiza tion problem is a generalization of the inverse problem.Given a partial solution?con tained in some feasible solutions?,the purpose of partial inverse problem is to modify the weight function so that there exists an optimal solution containing the partial solu tion with respect to the new weight function and minimizes the difference of the two weight functions.Spanning tree problem is a classical combinatorial optimization prob lem and its inverse and partial inverse problems have been widely studied.This thesis mainly studies the partial inverse maximum spanning tree problem?PIMST?.This thesis is divided into six chapters.In the first chapter,we first introduce the background,basic concepts and symbols of PIMST,and list the main contribution in this thesis.In the second chapter,we mainly study some basic properties of the optimal solu tion of PIMST with capacity constraint?CPIMST?.We also give the necessary and sufficient conditions for determining whether a given weight function is feasible or not with respect to fundamental cycle and fundamental cut.The CPIMST under the l_?-norm is studied in Chapter 3.Firstly,we find out the range of the optimal solution by using the properties of the optimal solution;Then,we present an exact algorithm to solve this problem by using the binary search method,and show its computational complexity is O?mnlog n?;Finally,we extend the algorithm to the CPIMST under the weighted l_?-norm.Chapter 4 studies the CPIMST with the partial solution only containing one edge.By fixing the value of ???e₀?,the problem is converted into several CPIMST^-;Then,find out the optimal solutions of these problems and choose the optimal one among these solutions as an approximate solution of CPIMST;Finally,by using the continuity of norm,we show the upper bound of the difference between the approximate solution and the optimal solution is??????-???e₀??where ? is the upper bound of value of the edge e₀ and ? is the number of CPIMST^-problems.In the fifth chapter,we mainly study the CPIMST^-when the partial solution con tains k edges,where k>0 is a fixed integer.First,we decompose the problem into several CPIMST^-subproblems whose partial solutions contain only one edge;Then,we use the previous algorithm to obtain the optimal solution for each subproblem;Fi nally,we obtain a feasible solution of the original problem through these optimal solu tions and prove that the upper bound of the approximation ratio is ???.Moreover,we extend the algorithm to the CPIMST.In the last chapter,we summarize the main results and discuss the future works.