# The inverse maximum flow problem considering l∞ norm

RAIRO - Operations Research (2008)

- Volume: 42, Issue: 3, page 401-414
- ISSN: 0399-0559

## Access Full Article

top## Abstract

top## How to cite

topDeaconu, Adrian. "The inverse maximum flow problem considering l∞ norm." RAIRO - Operations Research 42.3 (2008): 401-414. <http://eudml.org/doc/250416>.

@article{Deaconu2008,

abstract = {
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.
},

author = {Deaconu, Adrian},

journal = {RAIRO - Operations Research},

keywords = {Inverse combinatorial optimization; maximum flow; strongly polynomial time complexity.; inverse combinatorial optimization; strongly polynomial time complexity},

language = {eng},

month = {8},

number = {3},

pages = {401-414},

publisher = {EDP Sciences},

title = {The inverse maximum flow problem considering l∞ norm},

url = {http://eudml.org/doc/250416},

volume = {42},

year = {2008},

}

TY - JOUR

AU - Deaconu, Adrian

TI - The inverse maximum flow problem considering l∞ norm

JO - RAIRO - Operations Research

DA - 2008/8//

PB - EDP Sciences

VL - 42

IS - 3

SP - 401

EP - 414

AB -
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.

LA - eng

KW - Inverse combinatorial optimization; maximum flow; strongly polynomial time complexity.; inverse combinatorial optimization; strongly polynomial time complexity

UR - http://eudml.org/doc/250416

ER -

## References

top- R.K. Ahuja, T.L. Magnanti and J.B. Orlin, Network Flows. Theory, Algorithms and Applications, Prentice Hall, Englewood Cliffs, NJ (1993).
- R.K. Ahuja and J.B. Orlin, Combinatorial Algorithms for Inverse Network Flow Problems, Networks (2002). Zbl1026.90089
- R.K. Ahuja and J.B. Orlin, Inverse Optimization, Working Paper, Sloan School of Management, MIT, Cambridge, MA (1998).
- E. Ciurea and L. Ciupala, Sequential and Parallel Algorithms for Minimum Flows, J. Appl. Math. Comput.15 (2004) 53–75. Zbl1139.90335
- E. Ciurea and A. Deaconu, Inverse Minimum Flow Problem, J. Appl. Math. Comp., Korea23 (2007) 193–203. Zbl1131.90007
- A. Deaconu, The Inverse Maximum Flow Problem with Lower and Upper Bounds for the Flow, to appear in YUJOR18 (2008). Zbl1274.90057
- A. Deaconu, A Cardinality Inverse Maximum Flow Problem, Scientific Annals of Computer ScienceXVI (2006) 51–62.
- C. Heuberger, Inverse Combinatorial Optimization: A Survey on Problems, Methods, and Results, J. Combin. Optim.8 (2004) 329–361. Zbl1084.90035
- L. Liu and J. Zhang, Inverse Maximum Flow Problems under Weighted Hamming Distance, J. Combin. Optim.12 (2006) 395–408. Zbl1126.90070
- 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. Zbl0979.90119
- C. Yang and X. Chen, An Inverse Maximum Capacity Path Problem with Lower Bound Constraints, Acta Math. Sci., Ser. B22 (2002) 207–212. Zbl1006.90073
- C. Yang, J. Zhang and Z. Ma, Inverse Maximum Flow and Minimum Cut Problems, Optimization40 (1997) 147–170. Zbl0880.90041
- J. Zhang and C. Cai, Inverse Problems of Minimum Cuts, ZOR-Math. Methods Oper. Res.47 (1998) 51–58. Zbl0941.90013

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.