The idea of the inverse optimization problem is to adjust the values of the parameters so that the observed feasible solutions are indeed optimal. The modification cost is measured by different norms, such as l1, l2, l∞ norms and the Hamming distance, and the goal is to adjust the parameters as little as possible. In this paper, we consider the inverse maximum flow problem under the combination of the weighted l2 norm and the weighted Hamming distance, i.e., the modification cost is fixed in a given interval and depends on the modification out of the given interval. We present a combinatorial algorithm which can be finished in O(nm) to solve it due to the minimum cut of the residual network.
Long-Cheng Liu, Han Gao, Chao Li
. Inverse Maximum Flow Problem Under the Combination of the Weighted l2 Norm and the Weighted Hamming Distance[J]. Journal of the Operations Research Society of China, 2021
, 9(2)
: 465
-474
.
DOI: 10.1007/s40305-019-00273-w
[1] Ahuja, R.K., Magnant, T.L., Orlin, J.B.: Network Flows: Theory. Algorithms and Applications. Prentice-Hall, Englewood Cliffs (1993)
[2] Yang, C., Zhang, J.Z., Ma, Z.F.: Inverse maximum flow and minimum cut problems. Optimization 40, 147–170(1997)
[3] Liu, L.C., Zhang, J.Z.: Inverse maximum flow problems under the weighted Hamming distance. J. Comb. Optim. 12, 395–408(2006)
[4] Deaconu, A.: The inverse maximum flow problem with lower and upper bounds for the flow. Yugosl. J. Oper. Res. 18, 13–22(2008)
[5] Deaconu, A.: The inverse maximum flow problem considering l∞ norm. RAIRO Oper. Res. 42, 401–414(2008)
[6] Deaconu, A., Ciurea, E.: The inverse maximum flow problem under Lk norms. Carpathian J. Math. 28, 59–66(2012)
[7] Ciurea, E., Deaconu, A.: Inverse minimum flow problem. J. Appl. Math. Comput. 23, 193–203(2007)
[8] Güler, C., Hamacher, H.W.: Capacity inverse minimum cost flow problem. J. Comb. Optim. 19, 43–59(2010)
[9] Tayyebi, J., Aman, M.: Note on “Inverse minimum cost flow problems under the weighted Hamming distance”. Eur. J. Oper. Res. 234, 916–920(2014)
[10] Alizadeh, B., Burkard, R.E., Pferschy, U.: Inverse 1-center location problems with edge length augmentation on trees. Computing 86, 331–343(2009)
[11] Guan, X.C., Zhang, B.W.: Inverse 1-median problem on trees under weighted Hamming distance. J. Glob. Optim. 54, 75–82(2012)
[12] Nguyen, K.T., Sepasian, A.R.: The inverse 1-center problem on trees with variable edge lengths under Chebyshev norm and Hamming distance. J. Comb. Optim. 32, 872–884(2016)
[13] Nguyen, K.T., Vui, P.T.: The inverse p-maxian problem on trees with variable edge lengths. Taiwan. J. Math. 20, 1437–1449(2016)
[14] He, Y., Zhang, B.W., Yao, E.Y.: Weighted inverse minimum spanning tree problems under Hamming distance. J. Comb. Optim. 9, 91–100(2005)
[15] Liu, L.C., Wang, Q.: Constrained inverse min-max spanning tree problems under the weighted Hamming distance. J. Glob. Optim. 43, 83–95(2009)
[16] Liu, L.C., Yao, E.Y.: Inverse min-max spanning tree problem under the weighted sum-type Hamming distance. Theor. Comput. Sci. 396, 28–34(2008)
[17] Zhang, B.W., Zhang, J.Z., He, Y.: Constrained inverse minimum spanning tree problems under the bottleneck-type Hamming distance. J. Glob. Optim. 34, 467–474(2006)
[18] Liu, L.C., Yao, E.Y.: A weighted inverse minimum cut problem under the bottleneck type Hamming distance. Asia Pac. J. Oper. Res. 24, 725–736(2007)
[19] Zhang, J.Z., Cai, M.C.: Inverse problem of minimum cuts. Math. Methods Oper. Res. 47, 51–58(1998)
[20] Heuberger, C.: Inverse Optimization: a survey on problems, methods, and results. J. Comb. Optim. 8, 329–361(2004)
[21] Orlin, J.B.: Max flows in O(nm) time, or better. In: Proceeding of annual ACM symposium on theory of computing, pp. 765–774(2013)
