The lower bounded inverse optimal value problem on minimum spanning tree under unit l∞ norm

Abstract

We consider the lower bounded inverse optimal value problem on minimum spanning tree under unit l∞ norm. Given an edge weighted connected undirected network G=(V,E,w), a spanning tree T0, a lower bound vector l and a value K, we aim to find a new weight vector w¯ respecting the lower bound such that T0 is a minimum spanning tree under the vector w¯ with weight K, and the objective is to minimize the modification cost under unit l∞ norm. We present a mathematical model of the problem. After analyzing optimality conditions of the problem, we develop a strongly polynomial time algorithm with running time O(|V||E|). Finally, we give an example to demonstrate the algorithm and present the numerical experiments.