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.

Export metadata

  • Export Bibtex
  • Export RIS

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Cigdem Güler, Horst W. Hamacher
URN (permanent link):urn:nbn:de:hbz:386-kluedo-15882
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
Tag:inverse optimization ; maximum capacity path ; maximum flows ; minimum cut
Faculties / Organisational entities:Fachbereich Mathematik
DDC-Cassification:510 Mathematik

$Rev: 12793 $