On robust maximum flow with polyhedral uncertainty sets |
| |
Authors: | Michel Minoux |
| |
Institution: | (1) University Paris 6, 4 Place Jussieu, 75005 Paris, France |
| |
Abstract: | We address the problem of determining a robust maximum flow value in a network with uncertain link capacities taken in a polyhedral
uncertainty set. Besides a few polynomial cases, we focus on the case where the uncertainty set is taken to be the solution
set of an associated (continuous) knapsack problem. This class of problems is shown to be polynomially solvable for planar
graphs, but NP-hard for graphs without special structure. The latter result provides evidence of the fact that the problem
investigated here has a structure fundamentally different from the robust network flow models proposed in various other published
works. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|