Combinatorial algorithms for restricted inverse optimal value problems on minimum spanning tree under weighted l1 norm

Abstract

We study the restricted inverse optimal value problem on minimum spanning tree under weighted l 1 norm. In a connected edge-weighted network G (V, E, w), we are given a spanning tree T 0, a cost vector c and a value K. We aim to obtain a new weight vector w ̄ satisfying the bounded constraint such that T 0 is a minimum spanning tree under w ̄ whose weight is just K. We focus on minimizing the modification cost under weighted l 1 norm. We first convert its mathematical model into a linear programming problem (P). Then we solve its dual problem (D) by a sub-problem (D z∗) corresponding to the critical value z∗ which can be calculated by a binary search method. Impressively the sub-problem D z for z∈ R can be transformed into a minimum cost flow problem on an auxiliary network. Finally, we propose an O (| E| 2| V| 2 log| V| log (| V| c m a x)) algorithm, where c m a x is the maximum cost of the vector c.