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

Voir la notice de l'article provenant de la source Numdam

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
Keywords: 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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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

Cité par Sources :