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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Author:Cigdem Güler, Horst W. Hamacher
Serie (Series number):Report in Wirtschaftsmathematik (WIMA Report) (118)
Document Type:Preprint
Language of publication:English
Year of Completion:2009
Year of Publication:2009
Publishing Institute:Technische Universität Kaiserslautern
Date of the Publication (Server):2009/01/15
Tag:inverse optimization; maximum capacity path; maximum flows; minimum cut
Faculties / Organisational entities:Kaiserslautern - Fachbereich Mathematik
DDC-Cassification:5 Naturwissenschaften und Mathematik / 510 Mathematik
Licence (German):Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011