Combinatorial algorithms for solving the restricted bounded inverse optimal value problem on minimum spanning tree under weighted l∞ norm

Abstract

We consider the restricted bounded inverse optimal value problem on minimum spanning tree. In a connected undirected network G=(V, E, w), we are given a spanning tree T 0, a weight vector w, a lower bound vector l, an upper bound vector u, a cost vector c and a value K. We aim to obtain a new weight vector w ̄ satisfying the lower and upper bounds such that T 0 is a minimum spanning tree under the vector w ̄ with weight K. We aim to minimize the modification cost max e i∈ E c i| w ̄ i− w i| under weighted l∞ norm. We first analyze some properties of feasible and optimal solutions of the problem and develop a strongly polynomial time algorithm with running time O (m 2 n), where m=| E|, n=| V|. Then we reduce the time complexity to O (m 2 log n) by devising a more complex algorithm using a binary search method. Thirdly, we apply the first algorithm to the problem under unit l∞ norm, where c i= 1, and obtain an time algorithm. Finally, we give some examples to demonstrate the algorithms and present some numerical experiments to show the effectiveness of these algorithms.