The inverse maximum flow problem under weighted lk norm

Abstract

The problem consists in modifying the lower and the upper bounds of a given feasible flow f in a network G so that the given flow becomes a maximum flow in G and the distance between the initial vector of bounds and the modified one is measured using weighted L_knorm (k ∈ N) is minimum. We denote this problem by IMFWL_k. IMFWL_k is a generalization of the inverse maximum flow problem under the L_k norm (denoted IMFL_k, where the per unit cost of modification is equal to 1 on all arcs), which was previously studied and solved in polynomial time. In this paper, the algorithm for IMFLk is adapted to solve IMFWL_k.