Given a generalized minimum cost flow problem,the corresponding inverse problem is to find a minimal adjustment of the cost function so that the given generalized flow becomes optimal to the problem.In this paper,we c...Given a generalized minimum cost flow problem,the corresponding inverse problem is to find a minimal adjustment of the cost function so that the given generalized flow becomes optimal to the problem.In this paper,we consider both types of the weighted Hamming distances for measuring the adjustment.In the sum-type case,it is shown that the inverse problem is APX-hard.In the bottleneck-type case,we present a polynomial time algorithm.展开更多
文摘Given a generalized minimum cost flow problem,the corresponding inverse problem is to find a minimal adjustment of the cost function so that the given generalized flow becomes optimal to the problem.In this paper,we consider both types of the weighted Hamming distances for measuring the adjustment.In the sum-type case,it is shown that the inverse problem is APX-hard.In the bottleneck-type case,we present a polynomial time algorithm.
