Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
481062 | European Journal of Operational Research | 2010 | 5 Pages |
Abstract
Given a network N(V, A, u, c) and a feasible flow x0, an inverse minimum cost flow problem is to modify the cost vector as little as possible to make x0 form a minimum cost flow of the network. The modification can be measured by different norms. In this paper, we consider the inverse minimum cost flow problems, where the modification of the arcs is measured by the weighted Hamming distance. Both the sum-type and the bottleneck-type cases are considered. For the former, it is shown to be APX-hard due to the weighted feedback arc set problem. For the latter, we present a strongly polynomial algorithm which can be done in O(n · m2).
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Yiwei Jiang, Longcheng Liu, Biao Wu, Enyu Yao,