The inverse maximum flow problem considering l ∞ norm
RAIRO - Operations Research - Recherche Opérationnelle, Tome 42 (2008) no. 3, pp. 401-414.

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 O(m·log(n)) time complexity algorithm for solving this problem is presented, where m is the number of arcs and n 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 l ∞ norm is also studied.

DOI : 10.1051/ro:2008017
Classification : 90C27, 90C35, 68R10
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] R.K. Ahuja, T.L. Magnanti and J.B. Orlin, Network Flows. Theory, Algorithms and Applications, Prentice Hall, Englewood Cliffs, NJ (1993). | MR | Zbl

[2] R.K. Ahuja and J.B. Orlin, Combinatorial Algorithms for Inverse Network Flow Problems, Networks (2002). | MR | Zbl

[3] R.K. Ahuja and J.B. Orlin, Inverse Optimization, Working Paper, Sloan School of Management, MIT, Cambridge, MA (1998).

[4] E. Ciurea and L. Ciupala, Sequential and Parallel Algorithms for Minimum Flows, J. Appl. Math. Comput. 15 (2004) 53-75. | MR | Zbl

[5] E. Ciurea and A. Deaconu, Inverse Minimum Flow Problem, J. Appl. Math. Comp., Korea 23 (2007) 193-203. | MR | Zbl

[6] A. Deaconu, The Inverse Maximum Flow Problem with Lower and Upper Bounds for the Flow, to appear in YUJOR 18 (2008). | MR | Zbl

[7] A. Deaconu, A Cardinality Inverse Maximum Flow Problem, Scientific Annals of Computer Science XVI (2006) 51-62. | Zbl

[8] C. Heuberger, Inverse Combinatorial Optimization: A Survey on Problems, Methods, and Results, J. Combin. Optim. 8 (2004) 329-361. | MR | Zbl

[9] L. Liu and J. Zhang, Inverse Maximum Flow Problems under Weighted Hamming Distance, J. Combin. Optim. 12 (2006) 395-408. | MR | Zbl

[10] P.T. Sokkalingam, R.K. Ahuja and J.B. Orlin, Solving Inverse Spanning Tree Problems through Network Flow Techniques, Oper. Res. 47 (1999) 291-298. | MR | Zbl

[11] C. Yang and X. Chen, An Inverse Maximum Capacity Path Problem with Lower Bound Constraints, Acta Math. Sci., Ser. B 22 (2002) 207-212. | MR | Zbl

[12] C. Yang, J. Zhang and Z. Ma, Inverse Maximum Flow and Minimum Cut Problems, Optimization 40 (1997) 147-170. | MR | Zbl

[13] J. Zhang and C. Cai, Inverse Problems of Minimum Cuts, ZOR-Math. Methods Oper. Res. 47 (1998) 51-58. | MR | Zbl

Cité par Sources :