Inverse Generalized Minimum Cost Flow Problem Under the Hamming Distances

doi:10.1007/s40305-018-0231-5

Journal of the Operations Research Society of China ›› 2019, Vol. 7 ›› Issue (2): 355-364.doi: 10.1007/s40305-018-0231-5

所属专题： Discrete optimization

收稿日期:2017-12-08 修回日期:2018-09-10 出版日期:2019-06-30 发布日期:2019-06-30
通讯作者: Massoud Aman, Mobarakeh Karimi, Ardeshir Dolati E-mail:mamann@birjand.ac.ir;mobarake.karimi@birjand.ac.ir;dolati@shahed.ac.ir

Inverse Generalized Minimum Cost Flow Problem Under the Hamming Distances

Mobarakeh Karimi¹, Massoud Aman¹, Ardeshir Dolati²

1 Faculty of Mathematics and Statistics, University of Birjand, Birjand, Iran;
2 Department of Computer Science, Shahed University, Tehran, Iran

Received:2017-12-08 Revised:2018-09-10 Online:2019-06-30 Published:2019-06-30
Contact: Massoud Aman, Mobarakeh Karimi, Ardeshir Dolati E-mail:mamann@birjand.ac.ir;mobarake.karimi@birjand.ac.ir;dolati@shahed.ac.ir

摘要/Abstract

Abstract: 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.

Key words: Generalized minimum cost flow, Inverse problem, Hamming distance, Binary search

. [J]. Journal of the Operations Research Society of China, 2019, 7(2): 355-364.

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.

参考文献 10

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

Inverse Generalized Minimum Cost Flow Problem Under the Hamming Distances

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献 10

相关文章 0

编辑推荐

Metrics

本文评价