The Inverse Max Plus Sum Spanning Tree Problem By Modifying Sum-Weight Vector

In this paper, we consider the inverse max+sum spanning tree(IMSST) prob-lem by modifying the sum-cost vector. Given an edge-weighted undirected network G(V,E,c:ω), the max+sum spanning tree problem(MSST) is to find a spanning tree T which minimizes the combined weight maxe∈Tω(e)+∑e∈Tc(e).Whereas.the inverse max+sum spanning tree problem can be described as follows:To is a given non-optimal spanning tree in G, we need to adjust the cost c(e) of each edge to c(e) so that To becomes the max+sum spanning tree in G(V, E, c, ω). The objective func-tion is to minimize the cost incurred by modifying the cost vector under Hamming distance.In the first chapter, we review the research work of inverse optimization problem-s including the inverse spanning tree problems and list some important preliminary konwledge.In the second chapter, we study the IMSST by modifying the sum-cost vector under the bottleneck-type Hamming distance. First, we give the mathematical mod-el of the inverse problem, analyze the properties of its solution and the feasibility of the problem. Then we design a binary search algorithm to slove it within time com-plexity O(mlog~2(n)), where n is the number of nodes. Finally, we present numerical experiments and check the effectiveness of the algorithm.In the third chapter, we study the IMSST by modifying the sum-cost vector under the unit sum-type Hamming distance. First, we prove this problem is NP— hard, which means it is impossible to find an optimal solution in acceptable time. Then we analyze its inapproximability. At last, we find an approximate solution by taking its augmented problem as a medium.In the last chapter, we make a summary of this thesis and propose some relevant research work in the future.