Capacity inverse minimum cost flow problem

Çiğdem Güler () and Horst W. Hamacher
Additional contact information
Çiğdem Güler: University of Kaiserslautern
Horst W. Hamacher: University of Kaiserslautern

Journal of Combinatorial Optimization, 2010, vol. 19, issue 1, No 4, 43-59

Abstract: Abstract Given a directed graph G=(N,A) with arc capacities u ij and a minimum cost flow problem defined on G, the capacity inverse minimum cost flow problem is to find a new capacity vector $\hat{u}$ for the arc set A such that a given feasible flow $\hat{x}$ is optimal with respect to the modified capacities. Among all capacity vectors $\hat{u}$ satisfying this condition, we would like to find one with minimum $\|\hat{u}-u\|$ value. We consider two distance measures for $\|\hat{u}-u\|$ , rectilinear (L 1) and Chebyshev (L ∞) distances. By reduction from the feedback arc set problem we show that the capacity inverse minimum cost flow problem is $\mathcal{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.

Keywords: Inverse problems; Network flows; Minimum cost flows (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-008-9159-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:19:y:2010:i:1:d:10.1007_s10878-008-9159-8

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-008-9159-8

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().