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.
Mobarakeh Karimi, Massoud Aman, Ardeshir Dolati
. Inverse Generalized Minimum Cost Flow Problem Under the Hamming Distances[J]. Journal of the Operations Research Society of China, 2019
, 7(2)
: 355
-364
.
DOI: 10.1007/s40305-018-0231-5
[1] Ahuja, R.K., Magnanti, T.L., Orlin, J.B.:Network Flows:Theory, Algorithms, and Applications. Prentice Hall, New Jersey (1993)
[2] Ahuja, R.K., Orlin, J.B.:Inverse optimization. Oper. Res. 49, 771-783(2001)
[3] Aman, M., Tayyebi, J.:Capacity inverse minimum cost flow problem under the weighted Hamming distances. Iran. J. Oper. Res. 5, 12-25(2014)
[4] Guler, C., Hamacher, H.W.:Capacity inverse minimum cost flow problem. J. Comb. Optim. 19, 43-59(2010)
[5] Heuberger, C.:Inverse combinatorial optimization:a survey on problems, methods, and results. J. Comb. Optim. 8, 329-361(2004)
[6] Hochbaumand, D.S., Naor, J.:Simple and fast algorithms for linear and integer programs with two variables per inequality. SIAM. J. Comput. 23, 1179-1192(1994)
[7] Jiang, Y., Liu, L., Wuc, B., Yao, E.:Inverse minimum cost flow problems under the weighted Hamming distance. Eur. J. Oper. Res. 207, 50-54(2010)
[8] Liu, L., Yao, E.:Capacity inverse minimum cost flow problems under the weighted Hamming distance. Optim. Lett. 10, 1257-1268(2016)
[9] Tayyebi, J., Aman, M.:On inverse linear programming problems under the bottleneck-type weighted Hamming distance. Discr. Appl. Math (2016). https://doi.org/10.1016/j.dam.2015.12.017
[10] Zhang, J., Liu, Z.:Calculating some inverse linear programming problem. J. Comput. Appl. Math. 72, 261-273(1996)
