The problem is to modify the capacities of the arcs from a network so that a given feasible flow becomes a maximum flow and the maximum change of the capacities on arcs is minimum. A very fast time complexity algorithm for solving this problem is presented, where is the number of arcs and is the number of nodes of the network. The case when both, lower and upper bounds of the flow can be modified so that the given feasible flow becomes a maximum flow is also discussed. The algorithm proposed can be adapted to solve this problem, too. The inverse minimum flow problem considering norm is also studied.
Mots clés : inverse combinatorial optimization, maximum flow, strongly polynomial time complexity
@article{RO_2008__42_3_401_0,
author = {Deaconu, Adrian},
title = {The inverse maximum flow problem considering $l_{\infty }$ norm},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {401--414},
publisher = {EDP-Sciences},
volume = {42},
number = {3},
year = {2008},
doi = {10.1051/ro:2008017},
mrnumber = {2444495},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ro:2008017/}
}
TY - JOUR
AU - Deaconu, Adrian
TI - The inverse maximum flow problem considering $l_{\infty }$ norm
JO - RAIRO - Operations Research - Recherche Opérationnelle
PY - 2008
SP - 401
EP - 414
VL - 42
IS - 3
PB - EDP-Sciences
UR - http://www.numdam.org/articles/10.1051/ro:2008017/
DO - 10.1051/ro:2008017
LA - en
ID - RO_2008__42_3_401_0
ER -
%0 Journal Article
%A Deaconu, Adrian
%T The inverse maximum flow problem considering $l_{\infty }$ norm
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2008
%P 401-414
%V 42
%N 3
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro:2008017/
%R 10.1051/ro:2008017
%G en
%F RO_2008__42_3_401_0
Deaconu, Adrian. The inverse maximum flow problem considering $l_{\infty }$ norm. RAIRO - Operations Research - Recherche Opérationnelle, Tome 42 (2008) no. 3, pp. 401-414. doi : 10.1051/ro:2008017. http://www.numdam.org/articles/10.1051/ro:2008017/
[1] , and , Network Flows. Theory, Algorithms and Applications, Prentice Hall, Englewood Cliffs, NJ (1993). | MR | Zbl
[2] and , Combinatorial Algorithms for Inverse Network Flow Problems, Networks (2002). | MR | Zbl
[3] and , Inverse Optimization, Working Paper, Sloan School of Management, MIT, Cambridge, MA (1998).
[4] and , Sequential and Parallel Algorithms for Minimum Flows, J. Appl. Math. Comput. 15 (2004) 53-75. | MR | Zbl
[5] and , Inverse Minimum Flow Problem, J. Appl. Math. Comp., Korea 23 (2007) 193-203. | MR | Zbl
[6] , The Inverse Maximum Flow Problem with Lower and Upper Bounds for the Flow, to appear in YUJOR 18 (2008). | MR | Zbl
[7] , A Cardinality Inverse Maximum Flow Problem, Scientific Annals of Computer Science XVI (2006) 51-62. | Zbl
[8] , Inverse Combinatorial Optimization: A Survey on Problems, Methods, and Results, J. Combin. Optim. 8 (2004) 329-361. | MR | Zbl
[9] and , Inverse Maximum Flow Problems under Weighted Hamming Distance, J. Combin. Optim. 12 (2006) 395-408. | MR | Zbl
[10] , and , Solving Inverse Spanning Tree Problems through Network Flow Techniques, Oper. Res. 47 (1999) 291-298. | MR | Zbl
[11] and , An Inverse Maximum Capacity Path Problem with Lower Bound Constraints, Acta Math. Sci., Ser. B 22 (2002) 207-212. | MR | Zbl
[12] , and , Inverse Maximum Flow and Minimum Cut Problems, Optimization 40 (1997) 147-170. | MR | Zbl
[13] and , Inverse Problems of Minimum Cuts, ZOR-Math. Methods Oper. Res. 47 (1998) 51-58. | MR | Zbl
Cité par Sources :
