TY  - INPR
A1  - Güler, Cigdem
A1  - Hamacher, Horst
T1  - Capacity Inverse Minimum Cost Flow Problem
N2  - 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.
T3  - Report in Wirtschaftsmathematik (WIMA Report) - 111 
KW  - inverse problems
KW  - network flows
KW  - minimum cost flows
Y1  - 2007
UR  - https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1914
UR  - https://nbn-resolving.org/urn:nbn:de:hbz:386-kluedo-15097
ER  -