The inverse maximum flow problem under weighted l1 norm

Abstract

The problem introduced in this paper (denoted IMFW_∞) is to modify the capacities on arcs from a network so that a given feasible flow becomes a maximum flow and the maximum cost of change of the capacities is minimum. This problem is a generalization of the inverse maximum flow problem under l_∞ norm (denoted IMF_∞, where the per unit cost of modification is equal to 1 on all arcs), which was priviously studied and solved in polynomial time. In this paper, the algorithm for IMF_∞ is adapted to solve IMFW_∞.