Inverse max+sum spanning tree problem under weighted l∞ norm by modifying max-weight vector

Abstract

The max+sum spanning tree (MSST) problem is to determine a spanning tree T whose combined weight maxeeт w(e) + Σeer c(e) is minimum for a given edge-weighted undirected network G(V, E, c, w). This problem can be solved within O(m log n) time, where m and n are the numbers of edges and nodes, respectively. An inverse MSST problem (IMSST) aims to determine a new weight vector w so that a given T0 becomes an optimal MSST of the new network G(V, E, c, w). The IMSST problem under weighted l∞ norm is to minimize the modification cost maxeɛɛ q(e)|w(e) – w(e)], where q(e) is a cost modifying the weight w(e). We first provide some optimality conditions of the problem. Then we propose a strongly polynomial time algorithm in O(m2 log n) time based on a binary search and a greedy method. There are O(m) iterations and we solve an MSST problem under a new weight in each iteration. Finally, we perform some numerical experiments to show the efficiency of the algorithm.