Inverse Max+Sum Spanning Tree Problem By Modifying The Max-weight Vector Under L₁ Norm

In this paper,we consider the inverse max+sum spanning tree problems by mod-ifying the max-weight vector w under l1 norm.Given an edge-weighted undirected network G =(V,E,c,w),the max+sum spanning tree problem is to find a spanning tree T*which minimizes the combined weight maxe∈Tw(e)+∑e∈TC(e).The timecomplexity of this problem is O(m log n),where m is the number of edges and n is the number of nodes.Whereas,the inverse max+sum spanning tree problem can be described as follows:T0 is a given non-optimal spanning tree in G,we need to adjust the weight w(e)of edge e to w(e)so that T0 becomes an optimal max+sum spanning tree in the new network G=(V,E,c,w),and w-l≤w≤w+u,l≥0,u≥0.The objective function is to minimize the total cost incurred by modifying w under l1,norm,that is min ∑e∈E q(e)|w(e)-w(e)|,where q(e)is the cost of modifying one unit weight w(e).First of all,the model of the inverse max+sum spanning tree problem by modify-ing the max-weight vector w under l1 norm is built,and some symbols are introduced to simplify the model.Then we analyse the properties of the feasible solutions and the optimal solutions of the inverse problem,and the upper and lower bounds of the largest weight of tree edges are given at the same time.Next we consider the unbounded case of the inverse problem under the unit l1 norm.In this case,three methods to modify the weights of tree edges and non-tree edges are analysed con-cretely.And we design some subroutines to find the total increased amount of the weights of non-tree edges,which are based on the fundamental cuts and key edges respectively.Thus,a heuristic algorithm is given to solve the inverse problem.An-other algorithm which is based on the permutations of all non-tree edges is designed to make a comparison.And through several numerical experiments,the running results show that the heuristic algorithm we designed is really effective.