The search result changed since you submitted your search request. Documents might be displayed in a different sort order.
  • search hit 5 of 14
Back to Result List

Capacity Inverse Minimum Cost Flow Problem

  • Given a directed graph G = (N,A) with arc capacities u and a minimum cost flow problem defined on G, the capacity inverse minimum cost flow problem is to find a new capacity vector u' for the arc set A such that a given feasible flow x' is optimal with respect to the modified capacities. Among all capacity vectors u' satisfying this condition, we would like to find one with minimum ||u' - u|| value. We consider two distance measures for ||u' - u||, rectilinear and Chebyshev distances. By reduction from the feedback arc set problem we show that the capacity inverse minimum cost flow problem is NP-hard in the rectilinear case. On the other hand, it is polynomially solvable by a greedy algorithm for the Chebyshev norm. In the latter case we propose a heuristic for the bicriteria problem, where we minimize among all optimal solutions the number of affected arcs. We also present computational results for this heuristic.

Download full text files

Export metadata

Additional Services

Search Google Scholar
Metadaten
Author:Cigdem Güler, Horst Hamacher
URN:urn:nbn:de:hbz:386-kluedo-15097
Series (Serial Number):Report in Wirtschaftsmathematik (WIMA Report) (111)
Document Type:Preprint
Language of publication:English
Year of Completion:2007
Year of first Publication:2007
Publishing Institution:Technische Universität Kaiserslautern
Date of the Publication (Server):2007/12/03
Tag:inverse problems; minimum cost flows; network flows
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