Abstract:

We consider the bounded inverse optimal value problem on minimum spanning tree under unit $l_{\infty}$ norm. Given an edge weighted connected undirected network $G=(V, E, w)$, a spanning tree $T^0$, a lower bound vector $\bm{l}$, an upper bound vector $\bm{u}$ and a value $K$, we aim to obtain a new weight vector $\bm{\bar{w}}$ satisfying the lower and upper bounds such that $T^0$ is a minimum spanning tree under the vector $\bm{\bar{w}}$ with weight $K$. The objective is to minimize the modification cost under unit $l_{\infty}$ norm. We present a mathematical model of the problem. After analyzing optimality conditions of the problem, we develop an $O(|V||E|)$ strongly polynomial time algorithm.

Key words: minimum spanning tree, $l_\infty$ norm, inverse optimal value problem, strongly polynomial time algorithm