Inverse Tension Problems and Monotropic Optimization

  • Given a directed graph G = (N,A), a tension is a function from A to R which satisfies Kirchhoff\\\'s law for voltages. There are two well-known tension problems on graphs. In the minimum cost tension problem (MCT), a cost vector is given and a tension satisfying lower and upper bounds is seeked such that the total cost is minimum. In the maximum tension problem (MaxT), the graph contains 2 special nodes and an arc between them. The aim is to find the maximum tension on this arc. In this study we assume that both problems are feasible and have finite optimal solutions and analyze their inverse versions under rectilinear and Chebyshev distances. In the inverse minimum cost tension problem we adjust the cost parameter to make a given feasible solution the optimum, whereas in inverse maximum tension problem the bounds of the arcs are modified. We show, by extending the results of Ahuja and Orlin (2002), that these inverse tension problems are in a way \\\"dual\\\" to the inverse network flows. We prove that the inverse minimum cost tension problem under rectilinear norm is equivalent to solving a minimum cost tension problem, while under unit weight Chebyshev norm it can be solved by finding a minimum mean cost residual cut. Moreover, inverse maximum tension problem under rectilinear norm can be solved as a maximum tension problem on the same graph with new arc bounds. Finally, we provide a generalization of the inverse problems to monotropic programming problems with linear costs.

Volltext Dateien herunterladen

Metadaten exportieren

  • Export nach Bibtex
  • Export nach RIS

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar
Metadaten
Verfasserangaben:Cigdem Güler
URN (Permalink):urn:nbn:de:hbz:386-kluedo-15724
Schriftenreihe (Bandnummer):Report in Wirtschaftsmathematik (WIMA Report) (114)
Dokumentart:Preprint
Sprache der Veröffentlichung:Englisch
Jahr der Fertigstellung:2008
Jahr der Veröffentlichung:2008
Veröffentlichende Institution:Technische Universität Kaiserslautern
Datum der Publikation (Server):23.07.2008
Freies Schlagwort / Tag:cuts ; inverse problems ; monotropic programming; tension problems
Fachbereiche / Organisatorische Einheiten:Fachbereich Mathematik
DDC-Sachgruppen:5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik
Lizenz (Deutsch):Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011

$Rev: 13581 $