The inverse maximum flow problem under L_k norms

摘要

The problem consists in modifying the lower and 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 measured using L_k, norm (k ∈ N~*) is minimum. A fast apriori fesibility test is presented. An algorithm for solving this problem is deduced. Strongly and weakly polynomial time implementations of this algorithm are presented. Some particular cases of the problem are discussed.