Inverse Maximum Flow Problem Under the Combination of the Weighted l2 Norm and the Weighted Hamming Distance

doi:10.1007/s40305-019-00273-w

Journal of the Operations Research Society of China ›› 2021, Vol. 9 ›› Issue (2): 465-474.doi: 10.1007/s40305-019-00273-w

Inverse Maximum Flow Problem Under the Combination of the Weighted l₂ Norm and the Weighted Hamming Distance

Long-Cheng Liu¹, Han Gao¹, Chao Li²

1. School of Mathematical Sciences, Xiamen University, Xiamen 361005, Fujian, China;
2. School of Mathematics and Computer, Wuyi University, Wuyishan 354300, Fujian, China

Received:2018-05-16 Revised:2019-05-22 Online:2021-06-30 Published:2021-06-08
Contact: Long-Cheng Liu, Han Gao, Chao Li E-mail:longchengliu@xmu.edu.cn;30320142200012@stu.xmu.edu.cn;544941229@qq.com
Supported by:
This research is supported by the Fundamental Research Funds for the Central Universities (No.20720190068) and the China Scholarship Council (No.201706315073).

Abstract

Abstract: 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 l₁, l₂, 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 l₂ 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.

Key words: Maximum flow, Minimum cut, Inverse problem, Residual network, Strongly polynomial algorithm

CLC Number:

Long-Cheng Liu, Han Gao, Chao Li. Inverse Maximum Flow Problem Under the Combination of the Weighted l₂ Norm and the Weighted Hamming Distance[J]. Journal of the Operations Research Society of China, 2021, 9(2): 465-474.

TrendMD

References

[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 L_k 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)

Inverse Maximum Flow Problem Under the Combination of the Weighted l₂ Norm and the Weighted Hamming Distance

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 1

Recommended Articles

Metrics

Comments