A Study Of Constrained Inverse Minimum Flow Problems Under The Weighted Hamming Distance

In an inverse combinatorial optimization problem,a feasible solution is given and it is not optimal under the current parameters.The aim is to make the feasible solution optimal by modifying the current parameters as little as possible.The modification cost can be measured by different norms,such as weighted l1 norm,weighted l2 norm,weighted l∞ norm,weighted Hamming distance and so on.In this article,we focus on constrained inverse minimum flow problems under the weighted Hamming distance.In view of the general problem under the weighted bottleneck-type Hamming distance,by constructing the residual network N’(V,A’,u’,s,t)and modify it to weighted network N"(V,A",w,s,t),find a strong polynomial time algorithm 1 with O(m+N log N)time complexityit.For the sum-type constrained Inverse minimum flow problem under the weighted bottleneck-type Hamming distance,the algorithm 2 result proposed by L.C.Liu et al.[20]is used as the upper bound,and the result obtained by algorithm 1 is used as the lower bound.By using binary division method,the strong polynomial algorithm 3 with time complexity of O(nm log m)is obtained,and prove the effectiveness of the algorithm in three cases.For the the bottleneck-type constrained Inverse minimum flow problem under the weighted sum-type Hamming distance,a strong polynomial time algorithm 4 is obtained to solve the problem,and the time complexity is O(nm).