The Inverse Maximum Flow Problem With Lower and Upper Bounds for the Flow


Adrian Deaconu




The general inverse maximum flow problem (denoted GIMF) is considered, where lower and upper bounds for the flow are changed so that a given feasible flow becomes a maximum flow and the distance (considering $l_1$ norm) between the initial vector of bounds and the modified vector is minimum. Strongly and weakly polynomial algorithms for solving this problem are proposed. In the paper it is also proved that the inverse maximum flow problem where only the upper bound for the flow is changed (IMF) is a particular case of the GIMF problem.