The inverse maximum flow problem considering l∞ norm

Adrian Deaconu

RAIRO - Operations Research (2008)

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

Abstract

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

How to cite

top

Deaconu, 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
  1. R.K. Ahuja, T.L. Magnanti and J.B. Orlin, Network Flows. Theory, Algorithms and Applications, Prentice Hall, Englewood Cliffs, NJ (1993).  
  2. R.K. Ahuja and J.B. Orlin, Combinatorial Algorithms for Inverse Network Flow Problems, Networks (2002).  
  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.  
  5. E. Ciurea and A. Deaconu, Inverse Minimum Flow Problem, J. Appl. Math. Comp., Korea23 (2007) 193–203.  
  6. A. Deaconu, The Inverse Maximum Flow Problem with Lower and Upper Bounds for the Flow, to appear in YUJOR18 (2008).  
  7. A. Deaconu, A Cardinality Inverse Maximum Flow Problem, Scientific Annals of Computer ScienceXVI (2006) 51–62.  
  8. C. Heuberger, Inverse Combinatorial Optimization: A Survey on Problems, Methods, and Results, J. Combin. Optim.8 (2004) 329–361.  
  9. L. Liu and J. Zhang, Inverse Maximum Flow Problems under Weighted Hamming Distance, J. Combin. Optim.12 (2006) 395–408.  
  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.  
  11. C. Yang and X. Chen, An Inverse Maximum Capacity Path Problem with Lower Bound Constraints, Acta Math. Sci., Ser. B22 (2002) 207–212.  
  12. C. Yang, J. Zhang and Z. Ma, Inverse Maximum Flow and Minimum Cut Problems, Optimization40 (1997) 147–170.  
  13. J. Zhang and C. Cai, Inverse Problems of Minimum Cuts, ZOR-Math. Methods Oper. Res.47 (1998) 51–58.  

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.