Inverse Max+Sum Spanning Tree Problem By Modifying The Max-weight Vector Under Weighted L_? Norm

In this paper,we consider the inverse max+sum spanning tree problem by modify-ing the max-weight w vector.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?T w?e?+ ?e?Tc?e?.The time complexity of this prob-lem 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:T₀ is a given non-optimal spanning tree in G,we need to adjust the cost w?e?of each edge to ????e?so that To becomes the max+sum spanning tree in G?V,E,c,????.The objective function is to minimize the cost incurred by modifying w under l_? norm.In this paper,we first analyze the properties of the feasible solution and the optimal solution of the inverse problem.Then we obtain an important conclusion that we can construct a feasible solution through a given feasible objective function value.We considered three cases of the inverse problem.First,we considered the unbounded case of modified vectors under the unit l_? norm.We obtained the lower bound of the optimal objective value,followed by the method to get the final optimal objective value based on their properties.The number of iterations of the algorithm is no more than O?m?and time complexity is O?m² log n?.Under the weighted l_? norm,we first considered the unbounded case,then extended the results to the bounded case.We partitioned the edges in the given tree T₀ in two parts.We proposed different methods to find the optimal objective value in these two parts of edges.Both algorithms need to call O?m²?times of algorithms to solve the max+sum spanning tree problems and the time complexity is O?m³ log n?.