Research On Algorithms Of Several Network Improvement Problems

Network improvement problem is a hot topic in the field of optimization theory and it attracts many researchers in recent years. It is a kind of the generalized inverse optimization problem. The inverse optimization problem deals with how to change the parameters in the network,such that the given feasible solution becomes an optimal solution, and the modification cost is minimum. According to different backgrounds, the shortest path improvement problem, the inverse minimum cost flow problem and the inverse maximum flow problem are respectively studied, some theories and application achievements are obtained in network location and transportation network equilibrium. Network location problem is a classic problem in the field of optimization which mainly deals with how to find the the optimal locations for facilities in networks. As the surrounding environment may have changed, the facilities may already exist in real networks and deviate from the required optimal network location. However,the facilities can not be moved or the modification cost is too expensive,at this time, we should improve the network. This problem is called the inverse network location problem. In this paper, 1-maxian problem on special cycles under l1 norm and Hamming distance and two kinds of inverse minimum spanning tree problem are studied as follows:Firstly, we consider 1-maxian problem on special cycle under l1 norm.This problem is to modify the lengths of edges in a network under some given budget, such that the sum of the distances from the other vertices to the prespecified vertex become as big as possible. At first, we take special 4-cycle into account with uniform cost function and lengths increment upper bound 1, and obtain the optimal solutions under any budget. Then,we extend this problem to the special n-cycle case, and we also obtain theoptimal solutions under any budget.Secondly, we discuss 1-maxian problem on special cycle under Hamming distance. In the first place, we also take special 4-cycle into account with uniform cost function and lengths increment upper bound 1, and obtain the piecewise function of any budget and distance. Then, we extend the problem to this special n-cycle case, and obtain the optimal solutions under any budget.Thirdly, we study the inverse minimum spanning tree problem when weight increase is forbidden. This problem mainly considers how to reduce one or more edge weights in G as little as possible, such that the prespecified spanning tree T becomes a minimum spanning tree and the maximum weight reduction of the edges does not exceed a constant. We show that this problem can be solved in polynomial time. And we verify the efficiency of this algorithm by giving an example. We also consider the case that weight reduction is forbidden, and we also present polynomial time algorithm.