The inverse maximum flow problem considering l∞ norm
University “Transilvania” of Brasov, Faculty of Mathematics and Informatics, Theoretical Computer Science Departement, str. Iuliu Maniu 50, Brasov, Romania; firstname.lastname@example.org
Accepted: 28 March 2008
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.
Mathematics Subject Classification: 90C27 / 90C35 / 68R10
Key words: Inverse combinatorial optimization / maximum flow / strongly polynomial time complexity.
© EDP Sciences, ROADEF, SMAI, 2008