A Note On Inverse Max Flow Problem Under Chebyshev Norm

• In this paper, we study the inverse maximum flow problem under $$\ell_\infty$$-norm and show that this problem can be solved by finding a maximum capacity path on a modified graph. Moreover, we consider an extension of the problem where we minimize the number of perturbations among all the optimal solutions of Chebyshev norm. This bicriteria version of the inverse maximum flow problem can also be solved in strongly polynomial time by finding a minimum $$s - t$$ cut on the modified graph with a new capacity function.

Additional Services

Author: Cigdem Güler, Horst W. Hamacher urn:nbn:de:hbz:386-kluedo-15882 Report in Wirtschaftsmathematik (WIMA Report) (118) Preprint English 2009 2009 Technische Universität Kaiserslautern 2009/01/15 inverse optimization ; maximum capacity path ; maximum flows ; minimum cut Fachbereich Mathematik 5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011

$Rev: 13581$