The inverse maximum flow problem considering the l∞ norm

The problem is to modify the capacities of the arcs from a network so that a given feasible flow becomes a maximum flow and the maximum change of the capacities on arcs is minimum. A very fast O(m·log(n)) time complexity algorithm for solving this problem is presented, where m is the number of arcs and n is the number of nodes of the network. The case when both, lower and upper bounds of the flow can be modified so that the given feasible flow becomes a maximum flow is also discussed. The algorithm proposed can be adapted to solve this problem, too. The inverse minimum flow problem considering l∞ norm is also studied.