The inverse maximum flow problem considering <i>l</i>_∞ norm

作     者：Deaconu, Adrian 

作者机构：Univ Transilvania Brasov Fac Math & Informat Theoret Comp Sci Dept Brasov Romania 

出 版 物：《RAIRO-OPERATIONS RESEARCH》 (法国自动化、信息与运筹学；运筹学)

年 卷 期：2008年第42卷第3期

页      面：401-414页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070105[理学-运筹学与控制论] 0701[理学-数学] 

主　　题：inverse combinatorial optimization maximum flow strongly polynomial time complexity 

摘      要：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(infinity) norm is also studied.